Intro to Mergesort Algorithm

Mergesort is a sorting algorithm, a classic example of a divide and conquer sorting algorithm.
Divide and conquer is a technique to solve the problem by dividing it into smaller subsets which should be simple to easier to deal with.
The result of small problems now should help to solve bigger subsets and eventually the entire problem.
Let’s take a look at how mergesort works.

Mergesort Algorithm

The following is the steps for mergesort algorithm

1. Recursively divide the array into smaller sub-arrays until each array has a single element.
2. Recursively merge sub-arrays with sorted order until all the sub-arrays are merged. Note that when merging two arrays it’s essentially interleaving each element from the front of the list based on the sort order

Let’s take a look at an example picture to help better understand.

The above example shows you dividing (partitioning) steps.
It divides the initial array until a single element is left in a sub-array.

Now it just needs to merge each sub-array based on sorting order, either incremental or decremental, like the below picture.

Although I mentioned the array in the above example you can also sort a linked list with mergesort.
In some sense, it is more efficient to apply mergesort for linked list because you don’t need to have an extra buffer to store the temporary result.
The temporary buffer is necessary for sorting the array since you need to store merged sub-arrays as you see in the picture.
However, it is not necessary for linked list since you just need to decouple a node from the list and merge it later.

Code Example (Array)

void merge(vector<int> &array, int low, int middle, int high)
{
    // construct array 1, low to middle
    vector<int> array1;
    for (int i = low; i <= middle; ++i)
    {
        array1.push_back(array[i]);
    }
    
    // construct array 2, middle + 1 to high
    vector<int> array2;
    for (int i = middle + 1; i <= high; ++i)
    {
        array2.push_back(array[i]);
    }
    
    size_t array1Index = 0;
    size_t array2Index = 0;
    int resultIdx = low;
    
    while (array1Index < array1.size() && array2Index < array2.size())
    {
        if (array1[array1Index] < array2[array2Index])
        {
            array[resultIdx++] = array1[array1Index++];   
        }    
        else
        {
            array[resultIdx++] = array2[array2Index++];
        }
    }
    
    for (size_t i = array1Index; i < array1.size(); ++i)
    {
        array[resultIdx++] = array1[i];
    }
    
    for (size_t i = array2Index; i < array2.size(); ++i)
    {
        array[resultIdx++] = array2[i];
    }
}

void mergesort(vector<int> &array, int low, int high)
{
    if (low < high)
    {
        int middle = (low + high) / 2;
        mergesort(array, low, middle);
        mergesort(array, middle + 1, high);
        merge(array, low, middle, high);
    }
}

Code Example (Linked List)

struct Node
{
    int val;
    Node *next;
}

Node* mergesort(Node* head) 
{
    // no need to sort if null
    if (!head)
    {
        return 0;
    }
    // base case for recursive solution
    else if (!head->next)
    {
        return head;
    }

    Node *l1 = head;
    Node *l2 = mergesort(head->next);

    Node *newHead = 0;
    
    // merge two sorted linked lists 
    // (list with one node and list with multiple nodes)
    // l1 has one node and is smaller than all of l2
    // just append l2 to l1 and return
    if (l1->val < l2->val)
    {
        newHead = l1;
        newHead->next = l2;
        return newHead;
    }

    newHead = l2;

    // need to find a place to insert l1
    // this is essentially merging two sorted linked lists
    while (l2->next)
    {
        // found correct place to merge
        if (l1->val < l2->next->val)
        {
            Node *next = l2->next;
            l2->next = l1;
            l2->next->next = next;
            break;
        }

        l2 = l2->next;
    }

    if (!l2->next)
    {
        l2->next = l1;
        l1->next = 0;
    }

    return newHead;
}

Although it is not partitioning efficiently like an array it is still mergesort as it merges each sorted linked lists until done.
Here is the mergesort steps for linked list.

1. Iterate the list until the end
2. While winding up start merging two sorted lists
3. A list with one node (current node) and sorted linked lists from winding up process

IF you would like, You can also mergesort linked list by having additional arrays.

1. An array to hold each node of linked list
2. Iterate the array and start merging linked lists – index 0 and 1, 2 and 3 or 0, 1, 2, 3 whichever you prefer (this is the same as above except using an array.)

Performance

The performance of mergesort is O(n log n).
However, please note that you may need an extra buffer to store a temporary sorted result which may add copying cost.
You can avoid the extra buffer if you use linked list instead of array.

Conclusion

Mergesort is a classical divide and conquer sorting algorithm.
Although it is very easy to understand and implement it may cost more than other sorting algorithms due to extra buffer and copy cost.
But the performance is still bound under O(n log n) consistently unlike quicksort.