Mergesort C# and C++

Mergesort is another prominent sorting algorithm. Just like Quicksort its a divide and conquer based algorithm. However, unlike Quicksort, Mergesort is stable. Nonetheless, it is also recommended for larger collections. Run time for this algorithm is O(n log n), for best, average, and worst case. In terms of space complexity, Mergesort takes O(n) amount of space, worst case (this is due to the size of the array itself, the array is “n” amount of elements, we need to store the elements somewhere after sorting) .

Algorithm explained:

Merge Sort:

1. Divide Step

If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

To sort the entire sequence A[1 .. n], make the initial call to the procedure Mergesort (A, 1, n).

Mergesort(A, left, right)

1. IF left < right // Check for base case

2. THEN middle = FLOOR[(left + right)/2] // Divide step

3. MERGE (A, left, middle) // Conquer step.

4. MERGE (A, middle + 1, right) // Conquer step.

5. MERGE (A, left, middle, right) // Combine step.

Sample code in C#

        static public void DoMerge(int [] numbers, int left, int mid, int right)
        {

            int [] temp = new int[25];

            int i, left_end, num_elements, tmp_pos;

            left_end = (mid - 1);

            tmp_pos = left;

            num_elements = (right - left + 1);

            while ((left <= left_end) && (mid <= right))
            {

                if (numbers[left] <= numbers[mid])
                {
                    temp[tmp_pos++] = numbers[left++];
                }
                else
                {
                    temp[tmp_pos++] = numbers[mid++];
                }
            }

            while (left <= left_end)
            {
                temp[tmp_pos++] = numbers[left++];
            }

            while (mid <= right)
            {
                temp[tmp_pos++] = numbers[mid++];
            }

            for (i = 0; i < num_elements; i++)
            {

                numbers[right] = temp[right];
                right--;

            }

        }

        static public void MergeSort_Recursive(int [] numbers, int left, int right)
        {

          int mid;

          if (right > left)

          {

            mid = (right + left) / 2; //Divide step

            MergeSort_Recursive(numbers, left, mid);//Conquer step

            MergeSort_Recursive(numbers, (mid + 1), right);//Conquer step

            DoMerge(numbers, left, (mid+1), right);//Conquer step

          }

        }

C++:

int main()
{
	//assume vector 'items' is already filled with values
        vector<int> items();
	MergeSort(items, 0, items.size() - 1);
	return 0;
}
void MergeSort(vector<int> &items, int start, int end)
{
	if(start < end)
	{
		int mid = (start + end) / 2;
		MergeSort(items, start, mid);
		MergeSort(items, mid + 1, end);
		Merge(items, start, mid, end);
	}
}
void Merge(vector<int> &items, int start, int mid, int end)
{
	vector<int> temp(items.size());
	int first1 = start;
	int last1 = mid;
	int first2 = mid + 1;
	int last2 = end;

	int index = first1;
	while(first1 <= last1 && first2 <= last2)
	{
		if(items[first1] <= items[first2])
		{
			temp[index] = items[first1];
			first1++;
		}
		else
		{
			temp[index] = items[first2];
			first2++;
		}
		index++;
	}
	while(first1 <= last1)
	{
		temp[index] = items[first1];
		first1++;
		index++;
	}
	while(first2 <= last2)
	{
		temp[index] = items[first2];
		first2++;
		index++;
	}
	for(index = start; index < end; index++)
	{
		items[index] = temp[index];
	}
}

mergesort animation

Further illustrations

Mergesort description

recursive call tree

Interactive tutorial: http://www.contrib.andrew.cmu.edu/~askumar/mergeSort/mergeSort.html