Merge Sort

Notes

Merge sort is a recursive algorithm for sorting that decomposes the large problem of sorting an array into subproblems that are each a step closer to being solved.

The basic idea is to handle sorting by dividing an unsorted array in two and then sorting the two halves of that array recursively.

This is merge sort in pseudocode.

To sort the array, we must sort the left half, sort the right half, and then merge the two sorted halves. But how would we sort the left and right halves? Easy -- just break those subarrays in half as well, sort their respective left and right halves, and merge!

Let's use merge sort to sort the elements of this array in ascending order.

Keep halving the array until each subarray is of size 1 -- a subarray of size 1 is considered sorted.

Two sorted subarrays can be merged in O(n) time, by a simple algorithm:

Remove the smaller of the numbers at the start of each subarray and append it to the merged array, repeating until all elements of both subarrays are used up.

Here is one implementation of merge sort on an array that identifies the subarrays using pairs of integer indices into the array.

Merge sort requires O(nlog n) time in all cases. Since we divide each set to be sorted in half at each level of recursion, there will be log n levels. Then, at each level, a total of n comparisons must be made in order to merge subarrays. Hence, O(nlog n).

Since the best and worst case runtimes of merge sort are equivalent, the expected runtime is Θ(nlog n).

O(nlogn) is much more efficient than O(n2), which was the worst case runtime of bubble sort, insertion sort, and selection sort!

Here's a comparison of the runtimes of merge sort to the runtimes of other sorting algorithms covered in CS50.

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

(Merge) Sort the Array

Complete the implementation of merge sort to sort the array.

jharvard@run.cs50.net (~): ./a.out
4 15 16 50 8 23 42 108
4 8 15 16 23 42 50 108

Try out some pseudocode here!
#include <stdio.h>

#define SIZE 8

int temp[SIZE] = {0};

void merge (int array[], int start_1, int end_1, int start_2, int end_2)
{
    // TODO: Merge sorted subarrays using the auxiliary array 'temp'
}

void sort (int array[], int start, int end)
{
    if (end > start)
    {
        int middle = (start + end) / 2;

        // sort left half
        sort(array, start, middle);

        // sort right half
        sort(array, middle + 1, end);

        // merge the two halves
        merge(array, start, middle, middle + 1, end);
    }
}

int main(void)
{
    int numbers[SIZE] = { 4, 15, 16, 50, 8, 23, 42, 108};
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
    sort(numbers, 0, SIZE - 1);
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

Videos

study50 video thumbnail

Wednesday, Week 3

An introduction to sorting algorithms.
study50 video thumbnail

Rob's Merge Sort Short

Rob explains merge sort.