对此最好的排序方法？

Question

问题；

您必须按日期对一系列银行交易进行排序。他们中的大多数人(到目前为止)都井井有条，只有少数人出了问题。 您将在插入排序、选择排序和合并排序之间使用哪种排序算法来利用数组几乎已排序的事实？

我的回答(不确定是否正确)

假设N >= 5，我将从它的avg开始使用合并排序。时间复杂度为O(n * log n)，比插入排序O(n^2)更有效。但是，由于多个事务在相同的日期上，插入排序将是一种很好的稳定排序方法。

在这种情况下哪一种更好？合并还是插入排序？我朝正确的方向走了吗？

Answer 1

您应该选择插入排序，这不是因为稳定性，而是因为它是自适应的(请参阅这里)，并且由于输入一开始几乎是排序的，所以它的性能会更好。

这一“自适应”特征的含义是，已经存在的元素在O(1)时间被处理，并且非常接近其排序位置的元素也可以被认为是O(1) (直到某个k距离)。