5
$\begingroup$

A recent question on the complexity of sorting a countable infinite set (Sorting of countabe set) was apparently deleted. I'm curious why.

(Certainly, the question was poorly written, with no motivation or evidence that the OP had put any effort into answering it on their own; so it should have been (and was) closed. However, I think that there was a very interesting question lurking there, and left some comments in that direction, suggesting that the OP rewrite their question. Without knowing anything else, right now I think that question should have remained undeleted, to give the OP a chance to do so.)

EDIT: The text of the relevant question, as well as I can remember it, was: "Can a countable set be sorted in countable time? I know a finite set can be sorted in finite time, but is that still true for countable sets?" This question appears to me somewhat subtle, depending what order-type the set being sorted is allowed to have, and exactly what "countable time" means.

$\endgroup$
9
  • 7
    $\begingroup$ The user was deleted in a manner consistent with how we handle users with a background of misbehavior. It's harmless to undelete the question if you want. $\endgroup$
    – François G. Dorais Mod
    Commented Sep 29, 2013 at 21:05
  • $\begingroup$ Oh, okay, that's certainly something I didn't know. (Unfortunately, I don't think I have enough reputation to undelete the question.) If you post your comment as an answer, I'll accept it. $\endgroup$
    – Noah Schweber
    Commented Sep 29, 2013 at 21:07
  • $\begingroup$ @FrançoisG.Dorais: The user in question has number 40619, and has therefore joined just two days ago -- so how can he already have "a background of misbehavior"? -- Maybe with different accounts? $\endgroup$
    – Stefan Kohl Mod
    Commented Sep 29, 2013 at 21:32
  • 4
    $\begingroup$ @stefankohl: yes. $\endgroup$
    – François G. Dorais Mod
    Commented Sep 29, 2013 at 21:49
  • 1
    $\begingroup$ I note that the question has been undeleted. $\endgroup$
    – Gerry Myerson
    Commented Sep 29, 2013 at 23:27
  • $\begingroup$ The problem reminds me of old computer days, when we were asked for programming an sort-algorithm for arbitrary long streams of input data. This is in essence also the question for infinite sets. Standard solution was Merge/Sort with two tapes (or four, don't exactly remember) and although for an infinite input the overall time is infinite we are still making progress in this process, this shows that the answer must be positive. But is this really a question for this site? $\endgroup$
    – Gottfried Helms
    Commented Sep 30, 2013 at 0:47
  • $\begingroup$ @GottfriedHelms: Are you sure the answer is positive? How do you "sort" $\mathbb{Z}$ or $\mathbb{Q}$? If you try to wellorder them, the process won't stabilize. $\endgroup$
    – François G. Dorais Mod
    Commented Sep 30, 2013 at 1:01
  • $\begingroup$ @Francois: I think we can only discuss with respect to ordered subsets/partial sets and the time required for the ordering related to their cardinality. The time for Sort/merge is, if I recall right, with n as its cardinality something like $n* \ln(n)$, not even $n^2$, while -if I understand the intention of the phrase "uncountable time" in the question correctly at all- it would mean that the algorithm has something to do with $2^n$ instead (but a definition should explicitely occur in question) Because the input stream is infinite we have of course "never" the "complete order"/stability $\endgroup$
    – Gottfried Helms
    Commented Sep 30, 2013 at 1:32
  • $\begingroup$ ...(continued) but I think, the discussion of conceptual details were better in the question (if at all, and if the question is not on hold). But here is now late night and I should leave this forum and come back tomorrow... $\endgroup$
    – Gottfried Helms
    Commented Sep 30, 2013 at 1:37

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .