CODEWITHSUNDEEP
c#algorithmsortingmergesort
Coke
Coke

Reputation: 985

Simple Merge Sort in C#

I have been doing a small revision of sorting algorithms and came across with Merge Sort. I have written my code and have been modifying it for the last hour determining why it is not still working. I am getting standard StackOverFlow Exception. Can anyone advise me what's wrong with the algorithm? Thanks in advance. Here what I have managed to write so far:

public Int32[] MergeSort(Int32[] array)
{
    int counter = 0;
    if (array.Length == 0) { return array; }
    int mid = array.Length / 2;
    Int32[] leftHalf = new Int32[mid+1];
    Int32[] rightHalf = new Int32[mid+1];
    for (int i = 0; i < mid; i++) {
        leftHalf[i] = array[i];
    }
    for (int j = mid; j < array.Length; j++) {
        rightHalf[counter] = array[j];
        counter++;
    }
    counter = 0;
    MergeSort(leftHalf);
    MergeSort(rightHalf);
    return SortAndMerge(leftHalf,rightHalf);
}

public Int32[] SortAndMerge(Int32[] left, Int32[] right) {
    Int32[] myResult = new Int32[left.Length+right.Length];
    while (left.Length > 0 || right.Length > 0) {
        if (left.Length > 0 && right.Length > 0)
        {
            if (left[0] <= right[0])
            {
                myResult[myResult.Length] = left[0];
                int toRemoveIndex = Array.IndexOf(left, left[0]);
                left = left.Where((x, y) => y != toRemoveIndex).ToArray();
            }
            else
            {
                myResult[myResult.Length] = right[0];
                int toRemoveIndex = Array.IndexOf(right, right[0]);
                right = right.Where((z, g) => g != toRemoveIndex).ToArray();
            }

        }
        else if (left.Length > 0)
        {
            myResult[myResult.Length] = left[0];
            int toRemoveIndex = Array.IndexOf(left, left[0]);
            left = left.Where((x, y) => y != toRemoveIndex).ToArray();
        }
        else if (right.Length > 0) {
            myResult[myResult.Length] = right[0];
            int toRemoveIndex = Array.IndexOf(right, right[0]);
            right = right.Where((x, y) => y != toRemoveIndex).ToArray();
        }
    }
    return myResult;
}

Upvotes: 2

Views: 1343

Answers (2)

M.kazem Akhgary
M.kazem Akhgary

Reputation: 19179

if (array.Length == 0) return;

This is never true, thus the exception, because you always create array like this.

Int32[] leftHalf = new Int32[mid+1];

The minimum length is 1.

Check out correct merge sort algorithm here.

https://en.wikipedia.org/wiki/Merge_sort#Algorithm

Upvotes: 2

Ariwibawa
Ariwibawa

Reputation: 667

Do you mind refactoring? Why not use zip Here the sample from msdn

int[] numbers = { 1, 2, 3, 4 };
string[] words = { "one", "two", "three" };
var numbersAndWords = numbers.Zip(words, (first, second) => first + " " + second);
foreach (var item in numbersAndWords)
Console.WriteLine(item);

This code produces the following output:

1 one

2 two

3 three

There is also linq for sort.

Upvotes: 1

Related Questions