How to pair socks from a pile efficiently asks for an algorithm for sorting socks into pairs. On what basis is this on-topic for SO?

Should it not be migrated to Programmers, Computer Science or Theoretical Computer Science?

It asks for an algorithm with a certain efficiency.

Update : The OP has mentioned that he just wants a theoretical answer with an efficiency beating nlogn and not a practical solution. So, that "practical real-world question" is asking for an answer that may not necessarily be implementable.

  • 25
    Questions aren't off topic on SO just because they might be on topic on another site. – yannis Jan 20 '13 at 17:34
  • 2
    Not to mention that you really can't migrate it at this point. It has so many votes that it'll be fairly disruptive to the CSTheory community. – Mysticial Jan 20 '13 at 17:40
  • 17
    Since when is sorting a pile of socks research-level computer science? :p – ThiefMaster Jan 20 '13 at 17:41
  • 6
    It would become the most highly upvoted question on CS or CSTheory if migrated, so it definitely shouldn't be migrated now. – Bill the Lizard Jan 20 '13 at 17:41
  • 2
    I'm blown away by the fact the question is one day old and got that many votes. – Lance Roberts Jan 20 '13 at 17:42
  • 3
    @LanceRoberts It's on the front page of reddit.com/r/programming – Bill the Lizard Jan 20 '13 at 17:43
  • 12
    @nhahtdh It's a question about socks, so the votes are probably from sockpuppets /paranoia – yannis Jan 20 '13 at 17:49
  • 5
    @Yannis Did you just say that something is on-topic for the Programmers SE? What on earth is going on? – Bart Jan 20 '13 at 18:08
  • 2
    @Bart I even re-opened a question last night. There's only one explanation, tequila. ;P – yannis Jan 20 '13 at 18:10
  • 5
    Seriously? The obscene number of Reddit-driven upvotes (and joke answers) aside, it's a relief to see a thoughtful, well-written question that requires some expertise and brainpower like this on SO. If this is a candidate for closure, then SO isn't worth much any more. – jscs Jan 20 '13 at 23:20
  • 7
    @JoshCaswell It's a good question, sure, but that doesn't make it on-topic. – Gilles 'SO- stop being evil' Jan 21 '13 at 0:16
  • 5
    @Andrew: no, I just threw that on there to see if a bit of polite advice could avoid us having to lock it. – Shog9 Jan 21 '13 at 1:11
  • 3
    @CodeGnome: Historically, famous and hyper-high-scored questions have been allowed to evade the site's content rules/guidelines. I, like you, disagree with this pattern, though I can't see it changing any day soon. – Lightness Races in Orbit Jan 21 '13 at 3:31
  • 3
    I ran out of votes for the day downvoting the answers there...I mean seriously. Such a bad joke too... Worse, you know the question asker had no intent other than rep whoring when they protected their own question. – user7116 Jan 21 '13 at 15:18
  • 4
    @ThiefMaster sorting a pile of socks is research-level computer science by definition whenever and as soon as anyone asks for a research-level computer science solution to it. – ЯegDwight Jan 21 '13 at 21:27

It comes down to this: either the question is off-topic, or the FAQ is wrong/unclear/incomplete.

Either way there is something to fix.

  • 3
    No need for Off Topic, because it certainly meets the definition of Not Constructive. – user7116 Jan 21 '13 at 15:32
  • 2
    It's still open, what has the world become. Or, the FAQ is still wrong, what has the world become. – Pacerier Feb 23 '15 at 14:04

Algorithm questions are fine for Stack Overflow, even if they also fit on another site. That question is tagged appropriately: , and definitely .

  • 9
    Some language-agnostic questions related to sorting algorithm are on-topic, but not this one: it is not about a “software algorithm”, it isn't related to programming, any more than “how do I install Windows” is related to programming even if you're asking how to set up a machine that will be used by a developer. – Gilles 'SO- stop being evil' Jan 21 '13 at 0:17
  • 7
    "[Don't ask a]nything not directly related to writing computer programs" is clearly spelled out on the About page. Algorithms can certainly be on-topic, but the question as a whole does not qualify. – CodeGnome Jan 21 '13 at 2:47
  • 3
    I have to −1 because this is a tad too simplistic. What you're saying right now is that if I ask on SO for a recipe for a really tasty egg-salad sandwich, it will be perfectly on-topic as long as I tag it [algorithm] and [language-agnostic]. – ЯegDwight Jan 21 '13 at 21:17
  • As long as it meets the other criteria of the site. – Lance Roberts Jan 21 '13 at 21:42
  • If you ask how to make that egg-salad sandwich algorithmically through language-agnostic computer programming, it's on topic and correctly tagged. – Stuart P. Bentley Feb 7 '13 at 4:44


The question is not about a practical programming question that the author is facing. The most generous interpretation is that it is an abstract math problem without a concrete programming task to address.

Problems With This Question

  1. "What is the best way..." questions are usually polling questions, or questions that lead to extended debates about the definition of "best."
  2. It is not about a specific programming problem.
  3. It is not about a software algorithm.
  4. It is not about software tools commonly used by programmers.
  5. It is not a practical, answerable problem unique to the programming profession.
  6. It smells like a "g1v3 m3 d4 c0d3z" question.

At best, this is a brain teaser or an abstract math question, rather than a programming problem in search of a solution. It could certainly be edited or re-framed to be on-topic, but that would most likely ruin the original authorial intent.

None of this means it isn't well-written, or engaging. Clearly, many people think it's a fun or interesting question, and are up-voting it accordingly. However, popularity doesn't intrinsically make it on-topic.

What To Do About It

Perhaps there's a place elsewhere on Stack Exchange for it. Sadly, unless the question is rewritten as a programming question, it just doesn't belong here.

  • 2
    Can't say I completely agree here: 1) "How to" != "What's the best" 2) OP is looking for a programmic way to solve it. 3) OP is looking to do it with software. 4) True, but it doesn't need to be. 5) How is a pair matching algorithm not practical? 6) Kinda true. I'll give this one to you. – Mysticial Jan 21 '13 at 3:03
  • 2
    @Mysticial I appreciate the thoughtful response, but: 1) "what is the best way to pair them up efficiently with up to logarithmic extra space?" is an exact quote from the question; 2) OP specifically asks for a "general theoretical solution for a huge number of socks"; 3) OP doesn't mention "anything directly related to writing computer programs" (see stackoverflow.com/about). It's easy to get side-tracked by the fact that it's algorithmic, but it does not meet the criteria listed in our FAQ or About pages. – CodeGnome Jan 21 '13 at 3:15
  • 1
    1) That seems a bit more like nitpicking. 2) I don't see anything particularly bad about a general algorithm? He's asking for a general algorithm to a specific problem. 3) Under that argument, we might as well start by closing every single question here. – Mysticial Jan 21 '13 at 3:20
  • 2
    The FAQ, although it's been tightened up considerably over the years, does allow some leeway for things like this. He faced a real problem (one that many of us have), and is asking for a programmatic solution to it (naturally, one would have to assume the presence of some rather specialized hardware in order to actually implement it). That said, I appreciate this can be a bit of a stretch, so: meta.stackexchange.com/questions/164436/… – Shog9 Jan 21 '13 at 3:56
  • @Shog9 are you seriously expecting him to start hashing his socks from tomorrow ? – asheeshr Jan 21 '13 at 12:57
  • @Shog9 also, who decides how much of a stretch is allowed ? The opinion here suggests that is in fact off-topic however borderline it may be – asheeshr Jan 21 '13 at 12:59
  • 4
    @Shog9: amit is free to start a blog and put his sock curiosity on there... – user7116 Jan 21 '13 at 15:29

I agree that the question is off-topic. It is not about programming.

The question cannot be migrated to Computer Science (where it would be squarely on-topic), because it has had far too many votes. Migration retains the votes from the source site, which here would be highly disproportionate: there would be no way for the target community to rate the answers. The question cannot be migrated to Theoretical Computer Science because it is off-topic there (it is not a research-level question). I'm not familiar enough with Programmers to comment.

However, this is a good question that has had good answers, and while it is off-topic, it is close to the border: algorithms are strongly related to programming. So I am disinclined to close it. If I had seen it when it was initially posted, I would have voted to close it as off-topic, and requested a migration to Computer Science.

This is a case if there ever was one for adding a post notice (without the lock: there's no reason to prevent edits, votes or further answers) to indicate that this question is off-topic but kept around for historical reasons.

  • 8
    I'm pretty certain algorithms have never been off-topic on Stack Overflow. Ever. There are certainly other sites where there's considerably more focus on them, but that's irrelevant. – Shog9 Jan 21 '13 at 0:35
  • @Shog9, Who makes those decisions? Isn't it just left up to close/reopen votes and mods, case-by-case? For example, here's one... – The Community Jan 21 '13 at 0:45
  • 5
    Here's 24 thousand others – Shog9 Jan 21 '13 at 0:47
  • @TheCommunity: You're right, that should probably be "too localized: even if anyone is wondering the same thing, they'll never be able to find this question". – jscs Jan 21 '13 at 0:47
  • Those are just closed, not closed as off-topic. – The Community Jan 21 '13 at 0:47
  • Look closer, @The. – Shog9 Jan 21 '13 at 0:47
  • Ehh, open, whatever ;) – The Community Jan 21 '13 at 0:48
  • 4
    @Gilles: While you're right that "good" does not equal "on-topic", the question at hand is not about programming the same way a question about rubber-sheet gravity is not about astronomy. – jscs Jan 21 '13 at 0:49
  • 2
    @Shog9: Oh my dear...that tag is a close-vote sinkhole... – Time Traveling Bobby Jan 21 '13 at 14:57
  • A post notice without the lock would be a pretty good feature request, imo, for one-off questions like this that may not be good examples of what's on topic. – Adam Rackis Mar 29 '13 at 15:45

Here are some excerpts from the FAQ. Italicized comments are mine.

What kind of questions can I ask here?

  • a specific programming problem

Nope, this isn't one.

  • a software algorithm

Nope, it asks for an algorithm, but nowhere in the question is it applied to software.

  • software tools commonly used by programmers

Nope, just socks.

  • practical, answerable problems that are unique to the programming profession

Nope, impractical and not unique to programming.

What kind of questions should I not ask here?

You should only ask practical, answerable questions based on actual problems that you face.

Again, impractical. Just sort your socks.

Chatty, open-ended questions diminish the usefulness of our site and push other questions off the front page.

IMO this question fits the bill to a tee.

If your motivation for asking the question is “I would like to participate in a discussion about ______”, then you should not be asking here.

Sure looks like that's what's going on here. Many of the answers and comments are just attempts at humor, and are not really useful.

I'd think most people would be able to find something here to refute the legitimacy of this question if they wanted to badly enough.

  • 5
    In elementary school, maths is often taught with examples such as "Alice has 6 apples and she gives 2 each to Bob and Charlie. How many does she have left?". The idea is not to teach kids about apples or socialism, but to make the boring (for a 6 yr old) subject of addition/subtraction "fun" and "interesting". The socks here is just that — a little tale that allows everyone to personally relate to an otherwise dry question on algorithms. If you can't cut through the story to get to the point, then I suggest that you refrain from voting to close something that you know little about. – Lorem Ipsum Jan 20 '13 at 19:58
  • 8
    The part where you're wrong is "software algorithm"; the interpretation that's most commonly used is "algorithms that are used in software", not "algorithms that specifically deal with software". – casperOne Jan 20 '13 at 20:11
  • 3
    In other news, "Alice & Bob" stories are not actually soap operas. – Shog9 Jan 20 '13 at 20:14
  • 1
    Alright, so if you want to treat this as a serious question instead of a sort of joke conversation, is it not simply a duplicate of, say, this? – The Community Jan 20 '13 at 20:42
  • 1
    «*a specific programming problem Nope, this isn't one. *a software algorithm Nope, it's an algorithm, but not applied to software. » Are you kidding? You can't handle a simple analogy? – jscs Jan 20 '13 at 23:16
  • 2
    I can handle an analogy. I have a low tolerance for high-volume blatant trolling. And as I said, if you want to take it seriously, fine, let's close it as a duplicate. – The Community Jan 20 '13 at 23:18
  • The "trolling" is being handled as it comes in; there's a dozen deleted joke answers attached to the question (and you can contribute to comment cleanup, if you wish, by flagging). That will die down as the Reddit interest fades. I don't see any evidence of trolling on the part of the asker; e seems to be encouraging quality answers in comments. The duplicate you've suggested is a terrible question. It is related only in that it also falls under the topic of "sorting". – jscs Jan 20 '13 at 23:25
  • 1
    This is also a terrible question, I thought it was quite fitting. It is vague, it begs for discussion, and without having the slightest clue how it's supposed to be applied to actual software, it's impractical to try to answer it in a useful way. – The Community Jan 20 '13 at 23:26
  • 1
    I will concede that it's broad, but you have a very strange definition of "vague". «Given a pile of n pairs of socks, containing 2n elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space?» seems specific enough to me. And if you can't see how this could be applied to a programming problem, then I repeat my question about simple analogies. – jscs Jan 20 '13 at 23:30
  • 3
    It's vague because it's just an analogy that never ties in to reality, so you get all kinds of answers that just have an analogy to go on... so now we're monogramming socks and dying them different colors and so on, and at this point it's unclear how the extended analogy actually ties back in to software development. If it wasn't vague, this guy could have given one answer instead of three. – The Community Jan 21 '13 at 0:09
  • Does every correspondence really need to be spelled out explicitly? Monogramming/dying socks: add a pre-computed hash field to the data structure you're interested in sorting to speed up your comparisons. – jscs Jan 21 '13 at 0:54
  • It's also a question of whether the socks are already monogrammed/colored/whatever. Do they have distinguishable features? Does it matter if we pair a sock with a look-alike that is not actually its mate? How much space do we have available to make piles of socks? But yes, also, are we allowed to mark the socks, or will the wife yell at us? The question is silly. – The Community Jan 21 '13 at 1:18
  • «Do they have distinguishable features? Does it matter if we pair a sock with a look-alike...» How does our comparison function define equality? «How much space do we have available to make piles of socks?» This is already part of the question: "...with up to logarithmic extra space". «are we allowed to mark the socks, or will the wife yell at us?» Is the data structure even under our control, or does it, e.g., come from a web API so that we have to k̶e̶e̶p̶ ̶a̶ ̶l̶i̶s̶t̶ ̶o̶n̶ ̶a̶ ̶n̶o̶t̶e̶p̶a̶d̶ store our hashes somewhere else. Use your imagination a little here. – jscs Jan 21 '13 at 1:41
  • Josh Caswell, right... we likely wouldn't have to ask those questions if this were an actual software development question. Missed the part where the extra space question was handled though, good catch. – The Community Jan 21 '13 at 1:43
  • 3
    "Does it matter if we pair a sock with a look-alike that is not actually its mate?" — You are being intentionally dense here... The question is very clear when it says: "assume each sock has exactly one matching pair" Given this, pair(a, b) is a Boolean function and there is no ambiguity as to what should be done with a look-alike. – Lorem Ipsum Jan 21 '13 at 2:07

Not the answer you're looking for? Browse other questions tagged .