Что случилось с моим кодом сортировки слияния?

Question

Я изучаю код, и хотя я бы попытался написать алгоритм сортировки слияния (что-то, о чем мы слышали в нашем аналитическом курсе, но НЕ домашнее задание). Я работал от псевдокода, который показал нам тренер, но я не могу определить проблему. Любой шанс, который кто-то может указать мне в правильном направлении?

Редактировать: Алгоритм возвращает только первое значение в Списке.

static List<int> mergeSort(List<int> mj) 
{ 
    List<int>m = mj; 
    if(m.Count <= 1) 
     return m; 
    List<int> merge = new List<int>(); 

    List<int> left = new List<int>(); 
    List<int> right = new List<int>(); 
    int middle = m.Count/2; 

    for (int i = 0; i < middle; i++) 
     left.Add(m[i]); 
    for (int j = middle; j >= m.Count; j++) 
     right.Add(m[j]); 

    left = mergeSort(left); 
    right = mergeSort(right); 

    merge.AddRange(left); 
    merge.AddRange(right); 

    for (int k = 0; k < merge.Count; k++) 
    { 
     Console.Write(merge[k] + ","); 
    } 
    return merge; 

} 

Answer 1

Проблему с вашим кодом (помимо упоминания об ошибке Mike Cowan) заключается в том, что вы не выполняете какую-либо фактическую сортировку. Вы первые рекурсивно разделив свои списки в два раза (что правильно), но тогда вы просто конкатенации их вместе в их первоначальном порядке, в результате чего не добиться никакого результата:

merge.AddRange(left); 
merge.AddRange(right); 

Что вам нужно сделать, вместо этого итерации через два ваших подсписок (которые по индукции должны были соответственно сортироваться по рекурсивным вызовам) и добавлять элементы в объединенный список в порядке.

Мы начинаем путем сравнения 0 ^я элементов: left[0] против right[0]. Какой бы ни был из них меньше, добавляется в список merge, а счетчик его подстроки увеличивается. Предположим, что left[0] < right[0]: мы добавим left[0] в merge, и в следующей итерации нам нужно было бы рассмотреть left[1] против right[0]. Если left[1] снова меньше, добавим его в merge и на следующей итерации рассмотрим left[2] против right[0]. Если right[0] теперь является меньшим из двух, мы добавим его в merge и, в следующей итерации, сравните left[2] против right[1]. И так далее.

Это продолжается до тех пор, пока один из подсписок не будет исчерпан. Когда это произойдет, мы просто добавим все элементы из оставшегося списка в merge.

int leftIndex = 0;   
int rightIndex = 0; 

while (leftIndex < left.Count && rightIndex < right.Count) 
    if (left[leftIndex] < right[rightIndex]) 
     merge.Add(left[leftIndex++]); 
    else 
     merge.Add(right[rightIndex++]); 

while (leftIndex < left.Count) 
    merge.Add(left[leftIndex++]); 
while (rightIndex < right.Count) 
    merge.Add(right[rightIndex++]); 

Кроме того, вы не должны писать в консоль в вашего рекурсивного метода.Переместите Console.Write вызовы на метод Main:

static void Main(string[] args) 
{ 
    List<int> original = new List<int>(new int[] { 4, 75, 12, 65, 2, 71, 56, 33, 78,1, 4, 56, 85, 12, 5,77, 32, 5 }); 
    List<int> sorted = mergeSort(original); 

    for (int k = 0; k < sorted.Count; k++) 
     Console.Write(sorted[k] + ","); 
} 

Answer 2

Эта линия:

for (int j = middle; j >= m.Count; j++) 
    right.Add(m[j]); 

следует читать:

for (int j = middle; j < m.Count; j++) 
    right.Add(m[j]); 

Answer 3

Простой сортировка слиянием шаги

1. если (mj.length == 1) возвращение МДж;
2. Split в левые и правых списки и рекурсия
3. , когда левые и правые списки возвращения, объединить их < - вы не сделаете этот
4. возвращение присоединяемого левым и правых списки

Answer 4

Во-первых, линия

for (int j = middle; j >= m.Count; j++) 

должен быть

for (int j = middle; j < m.Count; j++) 

Кроме того, вы никогда не объединить левый и правый, вы» просто разместив их поверх каждого другого. Линия

merge.AddRange(left); 
merge.AddRange(right); 

Должно быть что-то вроде

mergeLeftRight(left, right) 

Где mergeLeftRight является второй функцией вы определяете, что делает фактическую сортировку. Прочтите статью в Википедии о сортировке Merge: http://en.wikipedia.org/wiki/Merge_sort