为什么插入排序总是在这个实现中跳动合并排序？(Why is insertion sort always beating merge sort in this implementation?)

我不明白：为什么我的插入排序实现每次都跳过合并排序，对于任何大小的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; }

I don't understand: why is my insertion sort implementation beating merge sort every time, for any size of 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; }

Here are my results:

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)

And the code for testing:

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(); }

In case anyone wondering I got these algorithms from Introduction to Algorithms, Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein (Author)

EDIT:

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; }