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

我想一个带有预处理的自然合并排序将在 O(n) 中完成。

1. 反转降序子数组中的顺序 - 总共 O(n)
2. 进行自然归并排序 - O(n)：http ://www.algorithmist.com/index.php/Merge_sort#Natural_mergesort

Answer 2

您需要Timsort，它利用自然运行。