问题标签 [mergesort]

I was recently brushing up on some fundamentals and found merge sorting a linked list to be a pretty good challenge. If you have a good implementation then show it off here.

我在一次采访中被问到这个问题。它们都是 O(nlogn)，但大多数人使用 Quicksort 而不是 Mergesort。这是为什么？

昨天我正在努力实现一个快速排序，然后我运行它，期望比 Mergesort 更快的运行时间（我也实现了）。我运行了这两个，虽然快速排序对于小于 100 个元素的较小数据集更快（并且我确实验证了它的工作原理），但合并排序很快成为更快的算法。有人告诉我，快速排序几乎总是比归并排序“更快”，而且我知道关于这个话题存在一些争论，但我至少预计它会比这更接近。对于 >10000 个元素的数据集，合并排序的速度提高了 4 倍以上。这是意料之中的，还是我的快速排序代码中有错误？

合并排序：

快速排序：

我认为是 MergeSort，即 O(n log n)。

但是，以下输出不同意：

我正在按序列号对 4 个节点的节点列表进行排序，并且排序正在进行 6 次比较。我很困惑，因为 6 > (4 log(4))。谁可以给我解释一下这个？

PS它是mergesort，但我仍然不明白我的结果。

谢谢大家的回答。谢谢汤姆纠正我的数学。

我正在编写一个合并排序函数，现在我只是在使用一个测试用例数组（没有输入 - 现在是静态的）。我不知道如何将数组作为参数传递。这是我现在的代码：

请注意，此 mergeSort 函数不起作用，因为我还没有弄清楚如何合并它们（这是我的任务）。我想在处理它之前对我的两个向量进行排序，但我无法编译它，因为我需要将数组作为参数传递。我不明白指针，所以如果这是解决方案，我的借口是无知。我现在正在学习编程，以 C++ 作为第一语言，并且只对语言的特性有一个基本的掌握。谢谢您的帮助。

我在一位教我 C++（作为第一语言）的朋友的指导下编写了递归函数。但是，我真的不明白发生了什么。他帮助我（以及 SO 社区）编写了一个归并排序函数。

在这个函数中，我分配：

这里到底发生了什么？它以 farray 和 sarray 作为参数调用 mergeSort 并更改值。mergeSort 递归地执行到自身多远？直到递归函数调用？

背景：

我正在清理大型（不能保存在内存中）制表符分隔的文件。当我清理输入文件时，我在内存中建立了一个列表；当它达到 1,000,000 个条目（大约 1GB 内存）时，我对其进行排序（使用下面的默认键）并将列表写入文件。此类用于将已排序的文件重新组合在一起。它适用于我迄今为止遇到的文件。到目前为止，我最大的案例是合并 66 个排序文件。

问题：

1. 我的逻辑是否存在漏洞（它在哪里脆弱）？
2. 我是否正确实现了合并排序算法？
3. 有什么明显的改进可以做的吗？

示例数据：

这是其中一个文件中的一行的抽象：

'hash_of_SomeStringId\tSome String Id\t\t\twww.somelink.com\t\tOtherData\t\n'

外卖是我'SomeStringId'.lower().replace(' ', '')用作我的排序键。

原始代码：

编辑：实施布赖恩的建议我想出了以下解决方案：

第二次编辑：根据John Machin的建议更新了代码：

粗略测试

使用相同的输入文件（2.2 GB 数据）：

• SortedFileMerger 类耗时 51 分钟（3068.4 秒）
• Brian的解决方案耗时 40 分钟（2408.5 秒）
• 添加John Machin的建议后，解决方案代码耗时 36 分钟（2214.0 秒）

我是一名 C++ 程序员，我写了这段代码来看看我是否能在功能上思考:) 有什么改进它的提示吗？

我已经实现了我认为是 python 中的合并排序算法。我以前从未在 Python 中编程过，所以我使用了一些资源和一些对我来说似乎很陌生的命令，以获得更好的理解。

但是，我也从来没有实现过归并排序，所以我不确定我是否正确地实现了它。任何指导、提示或更正将不胜感激。

这是我的合并方法：

同时，这是我的合并排序方法：

感谢您提供任何可能的帮助！:)

我是 Haskell 的新手，我正在尝试在其中实现一些已知的算法。

我已经对字符串实现了合并排序。与 C 和 Java 实现相比，我对 Haskell 实现的性能有点失望。在我的机器（Ubuntu Linux，1.8 GHz）上，C（gcc 4.3.3）在 1.85 秒内对 1 000 000 个字符串进行排序，Java（Java SE 1.6.0_14）在 3.68 秒内排序，Haskell（GHC 6.8.2）在 25.89 秒内排序。对于更大的输入（10 000 000 个字符串），C 需要 21.81 秒，Java 需要 59.68 秒，Haskell 开始交换，我更喜欢在几分钟后停止程序。

由于我是 Haskell 的新手，我很想知道我的实现是否可以提高时间/空间效率。

提前感谢您的任何提示乔治

我的实现：