问题标签 [mergesort]

任何人都知道在哪里可以找到一些关于 Tim Sort 的文档，使用示例和可能的伪代码来描述它？我对它的工作原理很感兴趣，但到目前为止我发现的文档，嗯，呃，阅读起来不太愉快^^。

我最近读了很多关于合并排序的文章，我想知道是否有一种方法可以在不使用至少一个额外数组的情况下进行合并排序。是否可以？

如何为 Java 实现并发快速排序或合并排序算法？

我们在一台 16 核（虚拟）内核的 Mac 上遇到了问题，其中只有一个内核（！）正在使用默认的 Java 排序算法工作，而且看到这台非常好的机器完全没有得到充分利用是不好的。所以我们写了自己的（我写的），我们确实获得了很好的加速（我写了一个多线程快速排序，由于它的分区性质，它可以很好地并行化，但我也可以写一个合并排序）......但我的实现只能扩展最多 4 个线程，它是专有代码，我宁愿使用一个来自信誉良好的来源的线程，而不是使用我重新发明的轮子。

我在网上找到的唯一一个例子是如何不在Java 中编写多线程快速排序，它是忙循环（这真的很糟糕），使用：

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

因此，除了无缘无故失去一个线程之外，它还确保通过在该 while 循环中忙循环来杀死性能（这令人难以置信）。

因此我的问题是：您是否知道 Java 中任何正确的多线程快速排序或合并排序实现都来自有信誉的来源？

我把重点放在我知道复杂性保持 O(n log n) 的事实上，但我仍然很高兴看到所有这些内核开始工作而不是空转。请注意，对于其他任务，在相同的 16 个虚拟内核 Mac 上，我通过并行化代码看到了高达 x7 的加速（而且我绝不是并发专家）。

因此，即使复杂度保持 O(n log n)，我也非常感谢 x7 或 x8 甚至 x16 的加速。

是否有关于如何实现 Arrays.sort(Object[] a) 使用的 mergeSort 的资源？虽然它的文档很好，但我很难理解它（特别是为什么在递归调用 mergeSort() 时会切换 src 和 dest ）。

我对 MergeSort 调用中第二个“B”和“C”参数的影响特别困惑。我需要它们，所以我可以访问它们以进行复制和合并，但是

我为这里的歧义道歉。这是输出：

显然这不是数组的正确结果，根据我的计数，反转应该等于 16。任何帮助或评论将不胜感激。（甚至是批评！；）

对平滑二维数组中的值进行排序的最快方法是什么？

输入是一个小的过滤图像：

• 约 60 x 80 像素
• 单通道
• 单精度或双精度浮点数
• 行主要存储，在内存中顺序
• 值有混合符号
• 分段“平滑”，区域宽度约为 10 像素

输出是已排序值的平面（大约 4800 个值）数组，以及对原始数组进行排序的索引。

我知道这个问题不太具体。

我想要的只是有人告诉我如何将普通的合并排序转换为就地合并排序（或具有恒定额外空间开销的合并排序）。

我所能找到的（在网上）只有页面说“它太复杂了”或“超出了本文的范围”。

唯一已知的就地合并方法（没有任何额外空间）太复杂而无法简化为实际程序。（取自这里）

即使它太复杂，如何使归并排序就地的基本概念是什么？

合并排序是否起作用；

获取值列表

把它分成两部分

取每个列表的第一个元素，最小值进入一个新列表（我猜从原始列表中删除）。比较接下来的两个数字 - 这样做直到一个列表为空，然后将另一个列表的其余部分放在 nw 列表的末尾？

另外，在链表上这样做有什么后果？

谢谢

它编译正确，但在执行时，我得到：

此应用程序已请求运行时以不寻常的方式结束它。

这是一个奇怪的错误。

代码有什么根本错误吗？

如果我们正在寻找线的交叉点（仅限水平线和垂直线）并且我们有 n 条线，其中一半是垂直的并且没有交叉点，那么

使用合并排序对 y 值上的行端点列表进行排序将花费 N log N

每次插入删除和搜索我们的数据结构（假设它是一个 b-tree）将是 < log n

所以总搜索时间将是 N log N

我在这里缺少什么，如果使用合并排序的时间需要 N log N 并且插入和删除需要 < log n 的时间，我们是否会丢弃常数因子以给出 N log N 的总时间。如果不是，那么< log n 怎么会在 ONotation 总运行时间中丢失？

谢谢