Merge Sort

Description

This algorithm makes multiple passes through the data set. In the first pass, it looks at adjacent pairs of data (the first and second, the third and fourth, the fifth and sixth, etc) and puts them in little sorted bundles of size 2. In the next pass, it looks at adjacent bundles (the first 2 and the next 2, the third bundle of 2 and the fourth bundle of 2, etc.) and orders them into sorted bundles of size 4. In the third pass, it again looks at adjacent bundles (this time of size 4) and orders them into sorted bundles of size 8. It continues this process until there are two bundles of size N/2; it orders them into a single bundle of size N, at which point the entire array is sorted. (N is the number of data items to sort.)

Animation

The Visual Sort section of this page contains small-scale, step-by-step animations of several sorting algorithms.

• Choose Merge Sort in the first drop-down menu.
• Repeatedly click on Step until you have a sense of how the algorithm works. Then click Run and check whether its continued behavior is what you expect.
• You can click on the New Sort button to get a new set of random data if you want to repeat the process to understand the algorithm better.

Performance

In each pass, it orders all N items from one size bundle to a bundle that is twice as large, so in each pass it looks at all N items. How many passes does it need? Well, the number of bundles is cut in half in each pass (for example, from 1000 to 500, to 250, to 125, to 63, to 32, to 16, to 8, to 4, to 2, to 1), so the number of passes is log₂(N), also known as lg(N).

Code

    // Merge Sort: Repeatedly merge small sorted subsets of the data into
    // larger sorted subsets, until the entire data set has been sorted.
    void sort(int[] data, int numItems)
    {
        // Create equal sized array in which to create merged sorted subsets.
        int[] sortedSubsets = new int[numItems];

        // Handle sorted subsets of size 1, then 2, then 4, then 8, etc.
        // (Subsets of size 1 are already "sorted".)
        for ( int subsetSize = 1; subsetSize < numItems; subsetSize *= 2 )
        {
            // Step through pairs of left and right subsets.
            for ( int leftIndex = 0; leftIndex < numItems;
                    leftIndex += 2 * subsetSize )
            {
                // For this particular left subset, where is the right subset?
                // (Don't go beyond edge of array with rightIndex or rightEdge.)
                int rightIndex = min(leftIndex + subsetSize, numItems);
                int rightEdge = min(rightIndex + subsetSize, numItems);

                // Merge the sorted left and right subsets to form a larger
                // sorted subset.
                merge(data, leftIndex, rightIndex, rightEdge, sortedSubsets);
            }

            // Copy all merged subsets back to original array before going
            // on to subsets that are twice as large.
            for ( int i = 0; i < numItems; i++ )
            {
                data[i] = sortedSubsets[i];
            }
        }
    }

    // Return the smaller of two values.
    int min(int value1, int value2)
    {
        if ( value1 <= value2 )
            return value1;
        else
            return value2;
    }

    // Merge two subsets of data into a sorted results array.
    // The left subset ranges from leftIndex to rightIndex - 1.
    // The right subset ranges from rightIndex to rightEdge - 1.
    void merge(int data[], int leftIndex, int rightIndex, int rightEdge,
               int results[])
    {
        int startRight = rightIndex;
        int resultsIndex;

        // Go through left and right subsets until we get to the end of one
        // of them, copying whichever value is smaller into results.
        for ( resultsIndex = leftIndex;
                leftIndex < rightIndex && rightIndex < rightEdge;
                resultsIndex++ )
        {
            if ( data[leftIndex] <= data[rightIndex] )
            {
                results[resultsIndex] = data[leftIndex];
                leftIndex++;
            }
            else
            {
                results[resultsIndex] = data[rightIndex];
                rightIndex++;
            }
        }
        // We have reached the end of one of the subsets, but there may 
        // be extra values in the other to copy over.

        // Whatever values are still in left subset, copy them to results.
        for ( ; leftIndex < startRight; leftIndex++, resultsIndex++ )
        {
            results[resultsIndex] = data[leftIndex];
        }

        // Whatever values are still in right subset, copy them to results.
        for ( ; rightIndex < rightEdge; rightIndex++, resultsIndex++ )
        {
            results[resultsIndex] = data[rightIndex];
        }
    }