最好的排序方法？
Best sorting method for this?
问题；
You have to sort an array of bank transactions by date. Most of them
are in order (by date), only a few are out of order.
Which sorting algorithm will you use between insertion sort, selection
sort and merge sort in order to take advantage of the fact that the
array is almost sorted?
我的回答（不确定是否正确）
假设 N >= 5，我会选择合并排序，因为它的平均值。时间复杂度为 O(n * log n)，这比插入排序 O(n^2) 更有效。但是，由于多个交易将在同一日期发生，插入排序将是一个很好的稳定排序方法。
在这种情况下，哪个更好？合并排序还是插入排序？我的方向对吗？
您应该选择插入排序，不是因为稳定性，而是因为它具有自适应性（请参阅 here），并且由于输入几乎从一开始就已排序，因此性能会更好。
这个"adaptive"特性的意思是，已经到位的元素在O(1)时间处理，非常接近其排序位置的元素也可以认为是O(1)（向上到某个 k 距离）。
问题；
You have to sort an array of bank transactions by date. Most of them are in order (by date), only a few are out of order.
Which sorting algorithm will you use between insertion sort, selection sort and merge sort in order to take advantage of the fact that the array is almost sorted?
我的回答（不确定是否正确）
假设 N >= 5，我会选择合并排序，因为它的平均值。时间复杂度为 O(n * log n)，这比插入排序 O(n^2) 更有效。但是，由于多个交易将在同一日期发生，插入排序将是一个很好的稳定排序方法。
在这种情况下，哪个更好？合并排序还是插入排序？我的方向对吗？
您应该选择插入排序，不是因为稳定性，而是因为它具有自适应性（请参阅 here），并且由于输入几乎从一开始就已排序，因此性能会更好。
这个"adaptive"特性的意思是，已经到位的元素在O(1)时间处理，非常接近其排序位置的元素也可以认为是O(1)（向上到某个 k 距离）。