c - 如何在合并排序和插入排序之间进行选择？

Question

我需要实现最快的排序算法来对使用 stdin 创建的链表进行排序。

我知道归并排序的时间复杂度是 O(n logn)，插入排序的时间复杂度是 O(n^2)(n 是链表中元素的数量)。

但是列表是通过标准输入创建的，因此，在未排序的列表上使用合并排序是否更有效，或者通过插入排序创建列表(这意味着在输入上对列表进行排序)更有效？

这是结构:

#define SIZE 50

struct node {
   int num;
   char name[SIZE];
   struct node* next;
};

这些是排序标准:

1. Sorted alphabetically by "name".
2. When the name is the same it's sorted by "num" (from higher to lower).

Answer 1

确实，插入排序是一种在线算法，而归并排序是一种离线算法。但是:

Not every offline algorithm has an efficient online counterpart.

这里也是如此。

当数据已经部分排序时，您应该更喜欢插入排序而不是合并排序，因为前者是自适应算法。

注意:插入排序也适用于 small sized inputs .