arrays - 如何对单调交替的数组进行排序

Question

有一个数组在一段时间内单调递增，然后递减，再次递增，...等，例如 [1,2,3,4,5,3,1,-1,-3,2,5,67,90,8,7,3,0] .对这个数组进行排序的最佳方法是什么？ Stackoverflow 中的一些相关问题建议 K-Way Merge Sort ，虽然没有提供实现细节。

那么排序它的理想方法是什么？任何巧妙的方法是否会提供比旧方法明显更好的性能O(N*log N)由 quicksort 提供，以便值得使用？如 K-Way Merge Sort是要做的事情，请提供一些实现细节，我在互联网上找不到!

Answer 1

您要Timsort ，利用自然运行。