algorithm - 使用插入排序有充分的理由吗？

Question

对于通用排序，答案似乎是否定的，因为快速排序、合并排序和堆排序往往在平均和最坏情况下表现更好。然而，插入排序似乎擅长增量排序，即在较长时间内一次向列表添加一个元素，同时保持列表已排序，特别是如果插入排序实现为链表 (O(log n) 平均情况与 O(n))。然而，堆似乎能够(或几乎)执行增量排序(从堆中添加或删除单个元素的最坏情况为 O(log n))。那么与其他基于比较的排序算法或堆相比，插入排序到底有什么优势呢？

Answer 1

来自 http://www.sorting-algorithms.com/insertion-sort :

Although it is one of the elementary sorting algorithms with O(n²) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.