Tag: C#

Flashcard: Mergesort

In this flashcard, we are going to look at the Merge algorithm.

What is Mergesort?

  • Mergesort is an efficient, recursive, divide-and-conquer sorting algorithm.

How does the Mergesort algorithm work?

  • First, the algorithm splits recursively the array in two sub-arrays until the length of each sub-array becomes one.
  • Next, the algorithm merges two sub-arrays at each recursion level into one array. Copying the elements of the sub-arrays into the new one, the algorithm sorts the elements. For that, it looks at the first element of both arrays, takes a smaller one, and removes that element from the sub-array. 
  • As a result, as soon the algorithm leaves the recursion the array is sorted.

What is the time complexity of the Mergesort algorithm?

  • Best O (n log n)
  • Average O (n log n)
  • Worst O (n log n)

What is the space complexity of the Mergesort algorithm?

  • O (n)

Is Mergesort a stable algorithm?

  • Yes, Mergesort belongs to the group of stable sorting algorithms.

What does a “stable sorting algorithm” mean?

  • Stable sorting algorithms preserve the order of input elements.

Provide an implementation of the Mergesort algorithm in C#.

int[] mergesort(int[] array)
{
    if (array == null || array.Length < 2) return array;

    int half = array.Length / 2;
    int[] left = array.Take(half).ToArray();
    int[] right = array.Skip(half).Take(array.Length - half).ToArray();

    left = mergesort(left);
    right = mergesort(right);

    array = merge(left, right);

    return array;
}

int[] merge(int[] left, int[] right)
{
    int totalSize = left.Length + right.Length;
    int[] array = new int[totalSize];

    int leftPointer = 0;
    int rightPointer = 0;

    for (int i = 0; i < totalSize; i++)
    {
        if(leftPointer >= left.Length)
        {
            array[i] = right[rightPointer];
            rightPointer++;
        }
        else if(rightPointer >= right.Length)
        {
            array[i] = left[leftPointer];
            leftPointer++;
        }
        else if(left[leftPointer] < right[rightPointer])
        {
            array[i] = left[leftPointer];
            leftPointer++;
        }
        else
        {
            array[i] = right[rightPointer];
            rightPointer++;
        }
    }

    return array;
}

The implementation encompasses two functions. The main function mergesort() is a recursive function. It checks first if the array is valid (means not null) and if it has more than one element. If the check fails, the function just returns what was passed in.

Next, the function splits the array recursively into two sub-arrays until the length of sub-arrays becomes 1. Starting from this point, the function starts to quit the recursion. Doing that, it merges the sub-arrays using the merge() function.

The merge() function takes two sub-arrays and merges them into one. During the merge, it sorts the elements of the sub-arrays. For that, we use two pointers that track positions in the sub-arrays. 

%d