排序解决方案已经提出，但排序有点太多了：我们不需要排序；我们只需要平等团体。

所以散列就足够了（而且更快）。

对于每种颜色的袜子，形成一堆。重复输入篮中的所有袜子，并将它们分配到颜色堆上。在每个桩上循环，并通过其他度量（例如模式）将其分配到第二组桩中递归地应用此方案，直到您将所有袜子分发到非常小的堆上，您可以立即进行可视化处理

当SQL Server需要对庞大的数据集进行哈希连接或哈希聚合时，这种递归哈希分区实际上是由它完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个CPU。

如果您可以找到一个分发密钥（哈希密钥），该密钥提供足够的存储桶，使得每个存储桶足够小，可以快速处理，那么您就不需要递归分区。不幸的是，我认为袜子没有这种特性。

如果每只袜子都有一个名为“PairID”的整数，那么可以根据PairID%10（最后一位）轻松地将它们分配到10个桶中。

我能想到的现实世界中最好的分区是创建一个堆积的矩形：一个维度是颜色，另一个是图案。为什么是长方形？因为我们需要O（1）随机访问桩。（3D长方体也可以，但这不太实用。）

更新：

并行性呢？多人能更快地匹配袜子吗？

最简单的并行化策略是让多个工人从输入篮中取出袜子，然后将袜子放到堆上。这只会增加这么多——想象100人在10个桩上战斗。同步成本（表现为手部碰撞和人类通信）破坏了效率和加速（参见通用可扩展性定律！）。这是否容易陷入僵局？不，因为每个工人一次只需要访问一堆。只有一个“锁”，就不会出现死锁。活锁可能是可能的，这取决于人类如何协调对桩的访问。他们可能只是使用随机退避，就像网卡在物理级别上那样，以确定什么卡可以独占地访问网络线路。如果它适用于NIC，那么它也应该适用于人类。如果每个工人都有自己的一组桩，它几乎可以无限扩展。然后，工人可以从输入篮中取出大块袜子（很少有人争抢，因为他们很少这样做），而且他们在分发袜子时根本不需要同步（因为他们有线程局部堆）。最后，所有工人都需要联合他们的桩组。我相信，如果工人形成一个聚合树，这可以在O（log（工人计数*每个工人的桩数））中完成。

元素的清晰度问题呢？正如文章所述，元素区别问题可以用O（N）来解决。袜子问题也是如此（如果你只需要一个分发步骤（我提出了多个步骤，只是因为人类不擅长计算-如果你在md5上分发（颜色、长度、图案…），即所有属性的完美哈希），那么一个步骤就够了）。

显然，一个速度不能比O（N）快，所以我们已经达到了最佳下限。

虽然输出不完全相同（在一种情况下，只是布尔值。在另一种情况中，是袜子对），但渐近复杂性是相同的。

考虑大小为“N”的哈希表。

如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）

我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章

让“N”对应于袜子独特颜色/图案数量的近似上限。

一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）

我希望我能为这个问题贡献一些新的东西。我注意到，所有的答案都忽略了这样一个事实，即在不降低整体洗衣性能的情况下，有两点可以执行预处理。

此外，即使是大家庭，我们也不需要假设有大量袜子。袜子从抽屉中取出并穿上，然后在洗衣服之前，将它们扔到一个地方（可能是一个垃圾箱）。虽然我不会将所说的垃圾箱称为后进先出堆栈，但我认为可以安全地假设

人们把两只袜子大致扔在箱子箱子在任何时候都不会随机化，因此从该容器顶部获取的任何子集通常都包含一双袜子。

由于我所知道的所有洗衣机的尺寸都是有限的（不管你要洗多少袜子），而且洗衣机中会发生实际的随机性，所以无论我们有多少袜子，我们总是有几乎不含单品的小子集。

我们的两个预处理阶段是“把袜子放在晾衣绳上”和“把袜子从晾衣绳里拿出来”，我们必须这样做，这样才能得到既干净又干燥的袜子。和洗衣机一样，晾衣绳是有限的，我假设我们可以看到袜子的整个部分。

以下是put_socks_on_ine（）的算法：

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

不要浪费时间四处移动袜子或寻找最佳搭配，这一切都应该在O（n）中完成，这也是我们将它们放在未分类的线上所需要的。袜子还没有配对，我们只有几个相似的簇。我们这里有一套有限的袜子是很有帮助的，因为这有助于我们创建“好”的簇（例如，如果这套袜子中只有黑色的袜子，那么按颜色簇就不是办法了）

下面是take_socks_from_line（）的算法：

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

我应该指出，为了提高其余步骤的速度，明智的做法是不要随机选择下一个袜子，而是从每个簇中依次选择一个又一个袜子。这两个预处理步骤只需要将袜子放在晾衣绳上或放在篮子里，这是我们无论做什么都必须做的，因此这将大大提高洗衣性能。

在此之后，很容易执行哈希分区算法。通常，大约75%的袜子已经配对，给我留下了非常小的袜子子集，并且这个子集已经（有点）聚类（在预处理步骤之后，我没有在我的篮子中引入太多熵）。另一件事是，剩余的集群往往足够小，可以一次处理，因此可以从篮子中取出整个集群。

下面是sort_maining_clusters（）的算法：

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

之后，只剩下几只袜子了。在这里，我将之前未配对的袜子引入到系统中，并在不使用任何特殊算法的情况下处理剩余的袜子——剩余的袜子非常少，可以非常快速地进行视觉处理。

对于所有剩余的袜子，我假设它们的同伴仍然没有洗，并将它们放在一边，以备下次迭代。如果你记录了一段时间内未配对袜子的增长（“袜子泄漏”），你应该检查你的垃圾箱——它可能会随机出现（你有猫睡在里面吗？）

我知道这些算法需要很多假设：一个充当某种LIFO堆栈的垃圾箱，一台有限的普通洗衣机，以及一条有限的普通晾衣绳——但这仍然适用于大量袜子。

关于并行性：只要你把两个袜子放在同一个箱子里，你就可以很容易地并行化所有这些步骤。

由于人脑的结构与现代CPU完全不同，所以这个问题毫无实际意义。

人类可以利用“找到匹配的对”这一事实来战胜CPU算法，这对于一个不太大的集合来说是一个操作。

我的算法：

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但通常很丰富。

两种思路，查找任何匹配项所需的速度，与查找所有匹配项所需要的速度相比，与存储相比。

对于第二种情况，我想指出一个GPU并行版本，它查询所有匹配的袜子。

如果您有多个要匹配的财产，则可以使用分组元组和更高级的zip迭代器以及推力的转换函数，尽管这里是一个基于GPU的简单查询：

//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>

// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator          GpuListIterator;

template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
    ColoredSockQuery( int colorToSearch )
    { SockColor = colorToSearch; }

    int SockColor;

    __host__ __device__
    bool operator()(T x)
    {
        return x == SockColor;
    }
};


struct GenerateRandomSockColor
{
    float lowBounds, highBounds;

    __host__ __device__
    GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};

    __host__ __device__
    int operator()(const unsigned int n) const
    {
        thrust::default_random_engine rng;
        thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
        rng.discard(n);
        return dist(rng);
    }
};

template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
    typedef typename std::iterator_traits<GpuListIterator>::value_type T;

    std::cout << name << ": ";
    thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    int numberOfSocks = 10000000;
    GpuList socks(numberOfSocks);
    thrust::transform(thrust::make_counting_iterator(0),
                      thrust::make_counting_iterator(numberOfSocks),
                      socks.begin(),
                      GenerateRandomSockColor(0, 200));

    clock_t start = clock();

    GpuList sortedSocks(socks.size());
    GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
                                                     socks.end(),
                                                     sortedSocks.begin(),
                                                     ColoredSockQuery<int>(2));
    clock_t stop = clock();

    PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);

    double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
    std::cout << "Time elapsed in ms: " << elapsed << "\n";

    return 0;
}

    //nvcc -std=c++11 -o test test.cu

1000万只袜子的运行时间：9毫秒

这是问错了问题。正确的问题是，我为什么要花时间整理袜子？如果你选择X个货币单位来计算你的空闲时间，那么每年的花费是多少？

通常情况下，这不仅仅是任何空闲时间，这是早晨的空闲时间，你可以躺在床上，或者喝咖啡，或者早点离开，不被交通堵塞。

退一步想办法解决问题通常是好的。

还有一个办法！

找一只你喜欢的袜子。考虑所有相关特征：不同照明条件下的颜色、整体质量和耐久性、不同气候条件下的舒适性以及气味吸收。同样重要的是，它们在储存过程中不应失去弹性，所以天然织物是好的，它们应该可以用塑料包装。

如果左脚和右脚的袜子没有区别，那就更好了，但这并不重要。如果袜子是左右对称的，找到一双袜子是O（1）运算，而对袜子进行排序是近似的O（M）运算，其中M是你家里扔袜子的地方的数量，理想情况下是一个小常数。

如果你选择了一双左右袜子不同的奇装异服，对左脚和右脚的桶进行全桶排序，取O（N+M），其中N是袜子的数量，M与上述相同。其他人可以给出找到第一双袜子的平均迭代次数的公式，但通过盲搜索找到一双袜子的最坏情况是N/2+1，对于合理的N来说，这在天文学上是不太可能的。当用Mk1 Eyeball扫描一堆未分类的袜子时，使用先进的图像识别算法和启发式方法可以加快速度。

因此，实现O（1）袜子配对效率的算法（假设对称袜子）为：

你需要估计你的余生需要多少双袜子，或者直到你退休并搬到更温暖的气候，不再需要穿袜子。如果你还年轻，你还可以估计我们需要多长时间才能在家里拥有袜子分拣机器人，而整个问题变得无关紧要。您需要了解如何批量订购您选择的袜子，以及它的价格，以及它们的送货方式。订购袜子！扔掉你的旧袜子。

另一个步骤3将包括比较几年来一次购买几双同样数量的可能更便宜的袜子的成本，并加上整理袜子的成本。但我要保证：批量购买更便宜！此外，库存袜子的价值会随着股价的上涨而增加，这比你在很多投资中得到的要多。此外，还有存储成本，但袜子确实不会占用壁橱顶部货架上的空间。

问题已解决。所以，只要买一双新袜子，扔掉/捐赠你的旧袜子，在知道你的余生每天都在节省金钱和时间之后，就可以幸福地生活下去。