Merge Sort

The array below holds a swimmer's five lap times.

int[] laps = {52, 47, 61, 39, 58};

The method below sorts the stretch of laps that starts at lo and ends at hi, both included.

public static void sortPart(int[] laps, int lo, int hi)
{
    if (lo < hi)
    {
        int half = (lo + hi) / 2;
        sortPart(laps, lo, half);
        sortPart(laps, half + 1, hi);
        merge(laps, lo, half, hi);
    }
}

When lo equals hi, the part is one element, which is already sorted, so the method does nothing, and that's the base case. Otherwise it sorts the left part, from lo through half, then the right part, from half + 1 through hi. Then the helper merge combines the two sorted parts. The whole array is sorted by sortPart(laps, 0, 4).

Merging two sorted parts compares the smallest unused value of each and takes the smaller. In the last merge of this sort, the left part holds 47, 52, and 61, and the right part holds 39 and 58.

Once one part is used up, everything left in the other part is at least as large as everything taken. It's already in order, so it's copied as it is. The merged values collect in a temporary array, which is copied back into the part of laps it came from.

The recursive calls run before the merge, and the first one finishes before the second starts. So the work begins at the left end of the array, several calls deep. Each call on a single element returns at once, so the table lists only the merges, in the order they happen.

The first merge puts 47 ahead of 52. The next two merges change nothing, because 61 already follows 52 and 39 already comes before 58. Only the last merge, the one in the merging table, changes every position. The two parts of a merge needn't be the same size. A part of 5 elements splits into 3 and 2, since half is (0 + 4) / 2, or 2.