merge sort\ in csharp

Here's an implementation of Merge Sort in C#:

main.cs
public static void MergeSort(int[] array)
{
    if (array.Length <= 1)
        return;

    int middleIndex = array.Length / 2;
    int[] leftArray = new int[middleIndex];
    int[] rightArray = new int[array.Length - middleIndex];

    Array.Copy(array, 0, leftArray, 0, middleIndex);
    Array.Copy(array, middleIndex, rightArray, 0, array.Length - middleIndex);

    MergeSort(leftArray);
    MergeSort(rightArray);

    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;

    while (leftIndex < leftArray.Length && rightIndex < rightArray.Length)
    {
        if (leftArray[leftIndex] < rightArray[rightIndex])
        {
            array[arrayIndex] = leftArray[leftIndex];
            leftIndex++;
        }
        else
        {
            array[arrayIndex] = rightArray[rightIndex];
            rightIndex++;
        }

        arrayIndex++;
    }

    while (leftIndex < leftArray.Length)
    {
        array[arrayIndex] = leftArray[leftIndex];
        leftIndex++;
        arrayIndex++;
    }

    while (rightIndex < rightArray.Length)
    {
        array[arrayIndex] = rightArray[rightIndex];
        rightIndex++;
        arrayIndex++;
    }
}
1176 chars
50 lines

To use this implementation, simply call the MergeSort method, passing in the array you wish to sort, like so:

main.cs
int[] arrayToSort = new int[] { 5, 2, 4, 6, 1, 3 };
MergeSort(arrayToSort);
76 chars
3 lines

Afterwards, the arrayToSort will be sorted in ascending order.

Note: This implementation works for arrays of any length, but is not optimized for very large arrays. If you need to sort large arrays, consider using an iterative implementation or a parallel version.

related categories

gistlibby LogSnag