This algorithms video tutorial explains how the merge sort algorithm sorts a linearly ordered set of elements into an ordered list. For simplicity, we assume that our list is an array. The basic idea behind the merge sort is that we can quickly merge two sorted arrays into one. This process is what we called the merging step.

To merge two sorted arrays, we index both arrays starting at zero, where the smallest element is located. Comparing the elements at each index, we choose the smaller element, put it into the array that we are merging into, and increment the index of the smaller element. By this method, we continually select the next smallest element from the two arrays and merge them into one sorted array.

Using the merge step, we can sort an unsorted array. We start by considering each element of the array to be a sorted array of length 1. Then we merge each pair of elements into an array of length two. Then pairs of arrays of length 2 can be merged into arrays of length 4, and so on until we reach the size of the array. Below we show the stages of the sort for an array of length 8 that is merge sorted by three merging step passes.

Lastly, we present a C++ implementation of our merge sort algorithm. This C++ code could be made more efficient by eliminating the dynamic allocation. However, we will put off such optimizations until a later lesson in favor of keeping the code simple for now.

#include <iostream>

void Merge(int* ipA, int iEnd1, int iEnd2) {
    int i = 0;
    int j = iEnd1;
    int k = 0;
    int* ipTemp = new int[iEnd2];
    // Take each next smallest element
    while (i < iEnd1 && j < iEnd2) {
        if (ipA[i] < ipA[j]) {
            ipTemp[k] = ipA[i];
            ++i;
        } else {
            ipTemp[k] = ipA[j];
            ++j;
        }
        ++k;
    }
    // Copy any remaining elements of the 1st array
    while (i < iEnd1) {
        ipTemp[k] = ipA[i];
        ++i;
        ++k;
    }
    // Copy any remaining elements of the 2nd array
    while (j < iEnd2) {
        ipTemp[k] = ipA[j];
        ++j;
        ++k;
    }
    // Copy the merged array back to the original
    for (int iIndex = 0; iIndex < iEnd2; ++iIndex) {
        ipA[iIndex] = ipTemp[iIndex];
    }
    delete [] ipTemp;
}

int main() {
    using namespace std;

    int iaArray[] = {24, 5, 3, 35, 14, 23, 19};
    int iSize = 7;

    // Merge Sort
    for (int i = 1; i < iSize; i *= 2) {
        for (int j = 0; j < iSize - i; j += 2*i) {
            int iEnd2 = (2*i < iSize - j) ? 2*i : iSize - j;
            Merge(&(iaArray[j]), i, iEnd2);
        }
    }

    // Output sorted array
    for (int i = 0; i < iSize; i++){
        cout << iaArray[i] << "  ";
    }
    cout << endl;

    return 0;
}