Exploring Merge Sort in C++

Welcome, aspiring programmer! Today's topic is Merge Sort. Merge Sort is a sorting technique similar to arranging a deck of shuffled cards in order. However, for data on an Internet scale, Merge Sort outperforms regular techniques. Today, we'll explore Merge Sort, code it in C++, and analyze its speed. Ready? Let's get started!

In computer science, Merge Sort is a popular method for sorting elements. Merge Sort uses the same 'divide-and-conquer' strategy for sorting as the familiar Quick Sort algorithm. In the three steps of Merge Sort:

1. Split the array into halves.
2. Sort each half separately.
3. Merge the sorted halves back together.

We will start by building code for merging two sorted parts. The merge process makes two halves play sort and seek. It compares elements from two halves and merges them so that the resulting list is sorted as well.

Let's code a merge() function in C++ that will do just that. Note that the final variant of the Merge Sort function will perform every operation "in place," meaning there will not be actual two arrays; we will operate on parts of one array. Bearing this in mind, let's implement the merge function to take just one array and treat its parts like separate arrays.

void merge(int arr[], int left, int mid, int right)
{
    int n1 = mid - left + 1; // Find number of elements in the left array
    int n2 = right - mid; // Find the number of elements in the right array

    int* Left = new int[n1]; // Define left array
    int* Right = new int[n2]; // Define right array

    // Let's fill in these arrays
    for (int i = 0; i < n1; i++)
        Left[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        Right[j] = arr[mid + 1 + j];
}

So far, we've divided our original list into two halves, Left and Right.

Now, we'll sort and merge these halves:

    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2)
    {
        if (Left[i] <= Right[j])
        {
            arr[k++] = Left[i++];
        }
        else
        {
            arr[k++] = Right[j++];
        }
    }
}

Seemingly tricky, the code is very straightforward:

• We place two pointers, i and j, at the beginning of the Left and Right arrays.

• We choose the smaller element, put it in the final array arr, and move the corresponding pointer further.

• We keep doing this until one of the pointers reaches the end of its array.