为什么插入排序总是在此实现中击败合并排序？
我不明白：为什么我的插入排序实现每次跳过合并排序，对于任何大小的n ？
public List InsertionSort(List elements, Boolean ascending = true) { for (Int32 j = 1; j = 0 && (elements[i].CompareTo(key) > 0) == ascending) elements[i + 1] = elements[i--]; elements[i + 1] = key; } return elements; }
public List MergeSort(List elements, Boolean ascending = true) { Sort(elements, 0, elements.Count - 1); return elements; } private void MergeSort(List 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 Merge(List elements, Int32 lowerBound, Int32 half, Int32 upperBound) { Int32 i = 0; Int32 j = 0; Int32 lowerElementsCount = half - lowerBound + 1; Int32 upperElementsCount = upperBound - half; List left = new List(); while (i < lowerElementsCount) left.Add(elements[lowerBound + i++]); List right = new List(); 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 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 GetFilledList(Int32 quantity, Int32 lowerBound, Int32 upperBound, Boolean mayRepeat = true) { List numbers = new List(); 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; }
因为，在合并排序之后，元素中的对象已经排序。 做另一个
elements = GetFilledList(i, 0, Int32.MaxValue, false);
之前
sw.Restart();
对10000个元素进行排序还不足以有效地评估算法。 走得更大
另外，输入是随机的吗？ 发布GetFilledList的实现
并且您需要在进行插入排序之前解除elements （或者只是重新初始化elements ）。
如果你翻转你进行排序的顺序，会发生什么？ 我猜你正在mergesort做所有的工作，然后插入排序只是排序已经排序的列表，它实际上非常擅长（O（n），假设一个理智的实现）。
对于小输入，插入排序应该比合并排序更快; 这就是O（N）的工作原理。
f(n) = O(g(n)) if for all n, greater than n0, f(n) < C * g(n)
具有良好复杂性的算法通常具有较高的C值，因此在获得大量输入之前，它们不会开始实际击败“较慢”的算法。
虽然esskar似乎找到了你所面临的主要问题，但请记住，将来你可能不得不用更多更大的输入来测试算法，以真正看到更好的算法闪耀。