为什么在这个实现中插入排序总是比归并排序更快？

Question

我不理解：为什么我的插入排序实现每次都能击败归并排序，无论n的大小是多少？

    public List<Int32> InsertionSort(List<Int32> elements, Boolean ascending = true)
    {
        for (Int32 j = 1; j < elements.Count; j++)
        {
            Int32 key = elements[j];
            Int32 i = j - 1;

            while (i >= 0 && (elements[i].CompareTo(key) > 0) == ascending)
                elements[i + 1] = elements[i--];

            elements[i + 1] = key;
        }

        return elements;
    }

---

    public List<Int32> MergeSort(List<Int32> elements, Boolean ascending = true)
    {
        Sort(elements, 0, elements.Count - 1);

        return elements;
    }

    private void MergeSort(List<Int32> elements, Int32 startIndex, Int32 count)
    {
        if(startIndex < count)
        {
            Int32 half = (startIndex + count).Divide(2, RoundMethod.Floor);
            Sort(elements, startIndex, half);
            Sort(elements, half + 1, count);
            Merge(elements, startIndex, half, count);
        }
    }

    public List<Int32> Merge(List<Int32> elements, Int32 lowerBound, Int32 half, Int32 upperBound)
    {
        Int32 i = 0;
        Int32 j = 0;

        Int32 lowerElementsCount = half - lowerBound + 1;
        Int32 upperElementsCount = upperBound - half;

        List<Int32> left = new List<Int32>();
        while (i < lowerElementsCount)
            left.Add(elements[lowerBound + i++]);

        List<Int32> right = new List<Int32>();
        while (j < upperElementsCount)
            right.Add(elements[half + j++ + 1]);

        left.Add(Int32.MaxValue);
        right.Add(Int32.MaxValue);

        i = 0;
        j = 0;

        for (int k = lowerBound; k <= upperBound; k++)
            if (left[i] <= right[j])
            {
                elements[k] = left[i];
                i++;
            }
            else
            {
                elements[k] = right[j];
                j++;
            }

        return elements;
    }

这是我的结果：

SORTING 1 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (1513 ticks)
INSERTION-SORT: TIME SPENT: 0ms (1247 ticks)

SORTING 10 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (2710 ticks)
INSERTION-SORT: TIME SPENT: 0ms (3 ticks)

SORTING 100 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (273 ticks)
INSERTION-SORT: TIME SPENT: 0ms (11 ticks)

SORTING 1000 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (3142 ticks)
INSERTION-SORT: TIME SPENT: 0ms (72 ticks)

SORTING 10000 ELEMENTS
MERGE-SORT: TIME SPENT: 18ms (30491 ticks)
INSERTION-SORT: TIME SPENT: 0ms (882 ticks)

---

测试代码：

    static void Main(string[] args)
    {
        for (int i = 1; i < 100000; i*=10)
        {
            List<Int32> elements = GetFilledList(i, 0, Int32.MaxValue, false);
            Console.WriteLine("SORTING {0} ELEMENTS", elements.Count);

            Stopwatch sw = new Stopwatch();

            //MERGE SORT
            sw.Start();
            new MergeSort().Sort(elements);
            sw.Stop();
            Console.WriteLine("MERGE-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);

            //INSERTION SORT
            sw.Restart();
            new InsertionSort().Sort(elements);
            sw.Stop();
            Console.WriteLine("INSERTION-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);
            Console.WriteLine();   
        }

        Console.ReadKey();
    }

如果有人想知道，我是从算法导论, Thomas H. Cormen (作者), Charles E. Leiserson (作者), Ronald L. Rivest (作者), Clifford Stein (作者)中获取这些算法的。

编辑：

    static List<Int32> GetFilledList(Int32 quantity, Int32 lowerBound, Int32 upperBound, Boolean mayRepeat = true)
    {
        List<Int32> numbers = new List<Int32>();

        Random r = new Random();
        for (int i = 0; i < quantity; i++)
        {
            Int32 numero = r.Next(lowerBound, upperBound); 

            while(!mayRepeat && numbers.Contains(numero))
                numero = r.Next(lowerBound, upperBound);

            numbers.Add(numero);
        }

        return numbers;
    }

- Renato Gama

Answer 1

因为在归并排序之后，元素中的对象已经被排序了。所以执行另外的排序是多余的。

elements = GetFilledList(i, 0, Int32.MaxValue, false);

之前的

sw.Restart();

- esskar

Answer 2

仅对10000个元素进行排序并不足以有效评估算法。要更大规模的测试。

此外，输入是否随机？请发布您的GetFilledList实现。

还有在进行插入排序之前需要对elements进行取消排序（或者重新初始化elements）。

如果您改变排序的顺序，会发生什么情况？我猜您正在使用归并排序完成所有工作，然后插入排序只是对已经排序好的列表进行排序，这种情况下插入排序实际上非常好（O（n），假设实现合理）。

- Michael Haren

Answer 3

对于小规模的输入，插入排序应该比归并排序更快；这是O(N)的工作方式。

f(n) = O(g(n)) if for all n, greater than n0, f(n) < C * g(n)

像拥有良好复杂度的算法通常具有更高的C值，因此它们只有在输入较大时才开始真正击败“较慢”的算法。

虽然esskar似乎已经找到了你面临的主要问题，但请记住，在未来，您可能需要测试具有更大输入的算法，以真正看到更好的算法表现。

- Adam Rackis