问题标签 [timsort]

我正在从这个链接 hacknoon Timsort学习Timsort

有一种说法“当运行次数等于或略小于 2 的幂时，合并 2 个数组效率更高。Timsort 选择 minrun 来尝试确保这种效率，方法是确保 minrun 等于或小于2的幂。”

为什么“当运行次数等于或略小于 2 的幂时，合并 2 个数组效率更高”？

在java中，该方法Arrays.sort有两个重载（我感兴趣，在这篇文章中）一个是用于原始类型，另一个是用于引用类型。他们使用不同的排序算法。

如何使用用于引用类型的算法对原始类型进行排序（既不使用列表将它们转换为引用类型）

该方法Arrays.sort(int[])使用 Dual-Pivot Quicksort。

该方法Arrays.sort(Object[])使用TimSort。

如果我有一个int[] array = { /* some values here */ };，如何使用 TimSort 对其进行排序？（我知道 usingInteger[] array = { /* some values here */ };将使用 TimSort 但我不希望这样做，因为使用对象而不是原始数据的开销，以后可能会有一些装箱和拆箱）

还是在原始数据上使用 TimSort 效率不高？

我为 TimSort java.util.TimSort找到了一个类，但我无法在我的代码中访问它。

这个问题的原因是 Quicksort 有一个最坏的情况，O(n^2)我遇到了一个利用这种情况的数组。虽然 TimSort 有一个最坏的情况(n log(n))和一个最好的情况O(n)

更新：

我实际上只对 TimSort 的内置方法感兴趣，它不需要是Arrays.sort. 如果有任何其他内置方法可以使用 TimSort 对原始数据类型进行排序，那么它是完全受欢迎的。

我知道有很多主题相同的主题，但在我看来，这个案例有点不同，并且在 javadocs 中没有详细记录。这是代码：

结果是异常：

所以看起来，在排序过程中不可能依赖收集，因为它处于脏状态。这种行为是否记录在某处？

我想在没有额外空间的情况下使用Python 3 in place对列表进行排序。

据我所知，Python 使用 对列表进行sorted(myList)排序，这会创建一个新的排序数组，显然会占用 O(N) 额外空间。或者使用myList.sort()which 使用Timsort，它也具有 O(N) 的最坏情况空间复杂度。

我搜索了文档，但没有找到任何用于常量空间算法的内置函数（选择排序、插入排序、shell 排序、堆排序、鸡尾酒排序等）

我知道我可以找到这些算法的实现，但内置的手动优化实现是我希望找到的最好的实现。

任何建议表示赞赏。

问题：在分块或生成块大小 [32-64 项] 的运行期间，timsort 如何识别最佳方法是搜索升序或降序运行？

示例：假设有一个块大小为 6 的数组进行排序。在提供的数据数组中遇到的一个 6 块如下所示。进一步假设数组是按升序排序的。

如果我们看到前两项 7、11 提供的提示，这是运行的增加子部分。在这一点上，考虑接下来的 4 项以确保我们维持或寻找增加的运行将是低效的，因为它实际上是一个递减的运行 [9, 6, 5, 2]。binaryInsertionSort 算法将按如下所示的递增顺序对其进行排序。

7

7、11

7、9、11

6、7、9、11

5、6、7、9、11

事实上，最有效的方法是。

7, 11 -> 一次完整的上升运行。

9, 6, 5, 2 -> 一个完整的下降运行。

合并 ([ 7, 11 ], [9, 6, 5, 2])

merge([7, 11], [2, 5, 6, 9]) //就地反转第二个数组。

问题：

对于给定的大小块 [例如：- 32 到 64 个项目]，Tim 排序实际上是否执行 (A) 或 (B)。即在满足块大小之前，它是否识别逐步查看每个项目并执行每个项目的 binaryInsertionSort 以构建排序的 Run ？

或者

它实际上是否首先扫描整个块以识别已经出现的自然排序子序列以有效地合并它们？

I'd like to sort a list and observe/visualize how Python's sorting algorithm Timsort is moving the elements around.

First attempt: A subclass of list which prints itself after each change:

That works when I change elements myself, but during sort ... nothing:

Second attempt: Print the list (in global variable a) at each comparison of elements:

That does something, but the list is always... empty?

Why do these attempts fail, and is there a way to observe what Timsort is doing?

如果我有这个函数 sorted(points, key=lambda point: point[axis])，时间复杂度仍然是 O(nlogn) 吗？

我知道sorted()使用 Timsort，它在一般情况下具有这种 Big-O 时间复杂度，但我不确定 lambda 函数如何增加它。返回一个值是 O(1) 但这应该为每个元素调用，所以n次。

这是否意味着时间复杂度为 O(n) + O(nlogn)？

我最近遇到了模式失败的快速排序（pdqsort）。 https://github.com/orlp/pdqsort https://github.com/stjepang/pdqsort

但是，我还没有找到任何对 pdqsort 进行概要分析的广泛研究，并将其与其他流行的 Timsort 进行比较。有谁知道这两种算法如何相互对抗？周围有纸吗？谢谢。

我已经为插入排序和合并排序编写了代码。现在我想实现我的插入排序并将排序合并为 Tim 排序。

我可以看到 Tim 排序的示例使用了 start、mid 和 end 输入，但应该可以在没有 no 的情况下做到这一点？

如果可能的话，我想保持我的合并和插入排序，因为输入输出非常适合我的其余代码。

我找到了 Tim sort 的这个例子，但我很纠结如何让它在我的代码中工作。

该算法的工作原理如下：

1. 我找到给定列表的最小值。
2. 然后弹出它并将其附加到另一个列表中。
3. 重复步骤 1 和 2，直到有一个元素，在这种情况下，我只需将其附加到另一个列表并结束程序。

问题

最后一个元素总是一些应该很久以前排序的随机数。

源代码