Повторяющиеся шаги в сортировке слияния

Question

Я пытаюсь вникать в некоторые алгоритмы и зацикливаться на сортировке слиянием. Я имею в виду, что это работает, но я регистрирую шаги этого алгоритма, и это заставляет его повторять те же шаги для тех же самых интервалов много раз. Правильно ли это и работает ли этот алгоритм?

К примеру, у меня есть массив:

new int[10] { 9, 4, 5, 3, 1, 2, 8, 7, 6, 0 }; 

И это алгоритм (взято отсюда http://www.c-sharpcorner.com/Blogs/14068/merge-sorting-algorithm-in-C-Sharp.aspx):

static void MergeSort(int[] a, int start, int end) 
{ 
    if (start != end) 
    { 
     int n = (start + end)/2; 

     MergeSort(a, 0, n); 
     MergeSort(a, n + 1, end); 

     MainMerge(a, start, (n + 1), end); 
    } 
} 

static public void MainMerge(int[] numbers, int left, int mid, int right) 
{ 
    t.Add(new Tuple<int, int>(left, right)); 

    int[] temp = new int[25]; 
    int i, eol, num, pos; 

    eol = (mid - 1); 
    pos = left; 
    num = (right - left + 1); 

    while ((left <= eol) && (mid <= right)) 
    { 
     if (numbers[left] <= numbers[mid]) 
      temp[pos++] = numbers[left++]; 
     else 
      temp[pos++] = numbers[mid++]; 
    } 

    while (left <= eol) 
     temp[pos++] = numbers[left++]; 

    while (mid <= right) 
     temp[pos++] = numbers[mid++]; 

    for (i = 0; i < num; i++) 
    { 
     numbers[right] = temp[right]; 
     right--; 
    } 
} 

t Вот только список запуска конечных tupples. Так что в конце концов я вижу в tMainMerge, что функция была вызвана для тех же значений, много раз:

-  t Count = 126 System.Collections.Generic.List<System.Tuple<int,int>> 
+  [0] {(0, 1)} System.Tuple<int,int> 
+  [1] {(0, 1)} System.Tuple<int,int> 
+  [2] {(0, 1)} System.Tuple<int,int> 
+  [3] {(0, 1)} System.Tuple<int,int> 
+  [4] {(0, 1)} System.Tuple<int,int> 
+  [5] {(0, 1)} System.Tuple<int,int> 
+  [6] {(0, 1)} System.Tuple<int,int> 
+  [7] {(0, 1)} System.Tuple<int,int> 
+  [8] {(0, 1)} System.Tuple<int,int> 
+  [9] {(0, 1)} System.Tuple<int,int> 
+  [10] {(0, 1)} System.Tuple<int,int> 
+  [11] {(0, 1)} System.Tuple<int,int> 
+  [12] {(0, 1)} System.Tuple<int,int> 
+  [13] {(0, 1)} System.Tuple<int,int> 
+  [14] {(0, 1)} System.Tuple<int,int> 
+  [15] {(0, 1)} System.Tuple<int,int> 
+  [16] {(0, 1)} System.Tuple<int,int> 
+  [17] {(0, 1)} System.Tuple<int,int> 
+  [18] {(0, 1)} System.Tuple<int,int> 
+  [19] {(0, 1)} System.Tuple<int,int> 
+  [20] {(0, 1)} System.Tuple<int,int> 
+  [21] {(0, 1)} System.Tuple<int,int> 
+  [22] {(0, 1)} System.Tuple<int,int> 
+  [23] {(0, 1)} System.Tuple<int,int> 
+  [24] {(0, 1)} System.Tuple<int,int> 
+  [25] {(0, 1)} System.Tuple<int,int> 
+  [26] {(0, 1)} System.Tuple<int,int> 
+  [27] {(0, 1)} System.Tuple<int,int> 
+  [28] {(0, 1)} System.Tuple<int,int> 
+  [29] {(0, 1)} System.Tuple<int,int> 
+  [30] {(0, 1)} System.Tuple<int,int> 
+  [31] {(0, 1)} System.Tuple<int,int> 
+  [32] {(0, 1)} System.Tuple<int,int> 
+  [33] {(0, 1)} System.Tuple<int,int> 
+  [34] {(0, 1)} System.Tuple<int,int> 
+  [35] {(0, 1)} System.Tuple<int,int> 
+  [36] {(0, 2)} System.Tuple<int,int> 
+  [37] {(0, 2)} System.Tuple<int,int> 
+  [38] {(0, 2)} System.Tuple<int,int> 
+  [39] {(0, 2)} System.Tuple<int,int> 
+  [40] {(0, 2)} System.Tuple<int,int> 
+  [41] {(0, 2)} System.Tuple<int,int> 
+  [42] {(0, 2)} System.Tuple<int,int> 
+  [43] {(0, 2)} System.Tuple<int,int> 
+  [44] {(0, 2)} System.Tuple<int,int> 
+  [45] {(0, 2)} System.Tuple<int,int> 
+  [46] {(0, 2)} System.Tuple<int,int> 
+  [47] {(0, 2)} System.Tuple<int,int> 
+  [48] {(0, 2)} System.Tuple<int,int> 
+  [49] {(0, 2)} System.Tuple<int,int> 
+  [50] {(0, 2)} System.Tuple<int,int> 
+  [51] {(0, 2)} System.Tuple<int,int> 
+  [52] {(0, 2)} System.Tuple<int,int> 
+  [53] {(0, 2)} System.Tuple<int,int> 
+  [54] {(0, 2)} System.Tuple<int,int> 
+  [55] {(0, 2)} System.Tuple<int,int> 
+  [56] {(0, 2)} System.Tuple<int,int> 
+  [57] {(0, 2)} System.Tuple<int,int> 
+  [58] {(0, 2)} System.Tuple<int,int> 
+  [59] {(0, 2)} System.Tuple<int,int> 
+  [60] {(0, 3)} System.Tuple<int,int> 
+  [61] {(0, 3)} System.Tuple<int,int> 
+  [62] {(0, 3)} System.Tuple<int,int> 
+  [63] {(0, 3)} System.Tuple<int,int> 
+  [64] {(0, 3)} System.Tuple<int,int> 
+  [65] {(0, 3)} System.Tuple<int,int> 
+  [66] {(0, 3)} System.Tuple<int,int> 
+  [67] {(0, 3)} System.Tuple<int,int> 
+  [68] {(0, 3)} System.Tuple<int,int> 
+  [69] {(0, 3)} System.Tuple<int,int> 
+  [70] {(0, 3)} System.Tuple<int,int> 
+  [71] {(0, 3)} System.Tuple<int,int> 
+  [72] {(0, 4)} System.Tuple<int,int> 
+  [73] {(0, 4)} System.Tuple<int,int> 
+  [74] {(0, 4)} System.Tuple<int,int> 
+  [75] {(0, 4)} System.Tuple<int,int> 
+  [76] {(0, 4)} System.Tuple<int,int> 
+  [77] {(0, 4)} System.Tuple<int,int> 
+  [78] {(0, 4)} System.Tuple<int,int> 
+  [79] {(0, 5)} System.Tuple<int,int> 
+  [80] {(0, 5)} System.Tuple<int,int> 
+  [81] {(0, 5)} System.Tuple<int,int> 
+  [82] {(0, 5)} System.Tuple<int,int> 
+  [83] {(0, 5)} System.Tuple<int,int> 
+  [84] {(0, 6)} System.Tuple<int,int> 
+  [85] {(0, 6)} System.Tuple<int,int> 
+  [86] {(0, 6)} System.Tuple<int,int> 
+  [87] {(0, 7)} System.Tuple<int,int> 
+  [88] {(0, 7)} System.Tuple<int,int> 
+  [89] {(0, 8)} System.Tuple<int,int> 
+  [90] {(0, 9)} System.Tuple<int,int> 
+  [91] {(2, 3)} System.Tuple<int,int> 
+  [92] {(2, 3)} System.Tuple<int,int> 
+  [93] {(2, 3)} System.Tuple<int,int> 
+  [94] {(2, 3)} System.Tuple<int,int> 
+  [95] {(2, 3)} System.Tuple<int,int> 
+  [96] {(2, 3)} System.Tuple<int,int> 
+  [97] {(2, 3)} System.Tuple<int,int> 
+  [98] {(2, 3)} System.Tuple<int,int> 
+  [99] {(2, 3)} System.Tuple<int,int> 
+  [100] {(2, 3)} System.Tuple<int,int> 
+  [101] {(2, 3)} System.Tuple<int,int> 
+  [102] {(2, 3)} System.Tuple<int,int> 
+  [103] {(3, 4)} System.Tuple<int,int> 
+  [104] {(3, 4)} System.Tuple<int,int> 
+  [105] {(3, 4)} System.Tuple<int,int> 
+  [106] {(3, 4)} System.Tuple<int,int> 
+  [107] {(3, 4)} System.Tuple<int,int> 
+  [108] {(3, 4)} System.Tuple<int,int> 
+  [109] {(3, 4)} System.Tuple<int,int> 
+  [110] {(3, 5)} System.Tuple<int,int> 
+  [111] {(3, 5)} System.Tuple<int,int> 
+  [112] {(3, 5)} System.Tuple<int,int> 
+  [113] {(3, 5)} System.Tuple<int,int> 
+  [114] {(3, 5)} System.Tuple<int,int> 
+  [115] {(4, 6)} System.Tuple<int,int> 
+  [116] {(4, 6)} System.Tuple<int,int> 
+  [117] {(4, 6)} System.Tuple<int,int> 
+  [118] {(4, 7)} System.Tuple<int,int> 
+  [119] {(4, 7)} System.Tuple<int,int> 
+  [120] {(5, 8)} System.Tuple<int,int> 
+  [121] {(5, 9)} System.Tuple<int,int> 
+  [122] {(6, 7)} System.Tuple<int,int> 
+  [123] {(6, 7)} System.Tuple<int,int> 
+  [124] {(7, 8)} System.Tuple<int,int> 
+  [125] {(8, 9)} System.Tuple<int,int> 
+  Raw View   

Например tupple 0-1 повторяется 35 раз! 35 раз только для сортировки первых 2 элементов? Я что-то упустил?

Answer 1

У вас ошибка в вашей реализации

Где у вас есть:

static void MergeSort(int[] a, int start, int end) 
{ 
    if (start != end) 
    { 
     int n = (start + end)/2; 

     MergeSort(a, 0, n); 
     MergeSort(a, n + 1, end); 

     MainMerge(a, start, (n + 1), end); 
    } 
} 

вы должны иметь

static void MergeSort(int[] a, int start, int end) 
{ 
    if (start != end) 
    { 
     int n = (start + end)/2; 

     MergeSort(a, start, n);   // <------------ HERE IS THE FIX 
     MergeSort(a, n + 1, end); 

     MainMerge(a, start, (n + 1), end); 
    } 
} 

Прямо сейчас вы собираетесь всю дорогу обратно в старте весь массив на каждом шагу.