CODEWITHSUNDEEP
c#algorithmmergesort
The_Cthulhu_Kid
The_Cthulhu_Kid

Reputation: 1859

What's Wrong with my Merge sort Code?

I am learning to code and I though I'd try writing a merge sort algorithm (something we heard about in our analytic course but NOT homework). I was working from the pseudo code the trainer showed us but I cannot identify the problem. Any chance someone could point me in the right direction?

edit: The algorithm only returns the first value in the List.

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;

}

Upvotes: 1

Views: 536

Answers (4)

Douglas
Douglas

Reputation: 54917

The problem with your code (apart from the bug Mike Cowan mentioned) is that you’re not performing any actual sorting. You’re first recursively splitting your lists in half (which is correct), but then you’re simply concatenating them back together in their original order, thereby achieving no result:

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

What you need to do instead is iterate through your two sublists (which, by induction, should have been respectively sorted in the recursive calls), and add elements to the merged list in order.

We start off by comparing the 0th elements: left[0] against right[0]. Whichever of the two is smaller, is added to the merge list, and its sublist’s counter is incremented. Suppose that left[0] < right[0]: we add left[0] to merge, and in the next iteration, we would then need to consider left[1] against right[0]. If left[1] is again smaller, we add it to merge and, in the next iteration, consider left[2] against right[0]. If right[0] is now the smaller of the two, we add it to merge and, in the next iteration, compare left[2] against right[1]. And so on.

This keeps going on until one of the sublists is exhausted. When that happens, we simply add all the elements from the remaining sublist into 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++]);

Additionally, you should not be writing to console within your recursive method. Move your Console.Write calls to your Main method:

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] + ",");
}

Upvotes: 6

Foggzie
Foggzie

Reputation: 9821

First off, the line

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

should be 

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

Also, you never actually merge the left and right, you're just placing them on top of eachother. The line

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

Should be something like 

mergeLeftRight(left, right)

Where mergeLeftRight is a second function you define that does the actual sorting. Read the wikipedia article on Merge Sorts: http://en.wikipedia.org/wiki/Merge_sort

Upvotes: 4

The Real Baumann
The Real Baumann

Reputation: 1961

Simple merge sort steps

  1. if( mj.length == 1 ) return mj;
  2. Split into left and right lists and recurse
  3. when left and right lists return, merge them <-- you do not do this
  4. return merged left and right lists

Upvotes: 2

Mike Cowan
Mike Cowan

Reputation: 919

This line:

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

should read:

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

Upvotes: 5

Related Questions