4.3.5.1–4.3.5.2 - Bubble sort and merge sort (Java)

Bubble passes and swaps

Bubble sort repeatedly compares adjacent items and swaps an out-of-order pair, moving the largest remaining item to the end of each ascending pass.

In [6,2,5,1], pass1 compares6/2, then6/5, then6/1: the array becomes [2,5,1,6]. The final6 is now fixed. Pass2 need only scan the first three items, producing [2,1,5,6]; pass3 produces [1,2,5,6]. A pass includes a sequence of comparisons, not just one swap.

This method belongs inside a Java class. end is the last index of the unsorted region. With zero or one item, the outer loop performs no work.

static void bubbleSort(int[] a) {
    for (int end = a.length - 1; end > 0; end--) {
        boolean swapped = false;
        for (int i = 0; i < end; i++) {
            if (a[i] > a[i + 1]) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

A pass with no swaps proves every adjacent pair in the remaining region is ordered, so this version can stop. Worst-case comparisons are about $(n-1)+(n-2)+\cdots+1=n(n-1)/2$, giving $O(n^2)$. Bubble sort is a particularly inefficient choice for large random/reversed data. The no-swap optimisation gives $O(n)$ best-case time on already ordered data; a fixed-pass version without that optimisation still does quadratic comparisons. To sort descending, swap when the left value is smaller; the smallest then moves to the end.

Merge and divide-and-conquer

Merge sort divides a sequence into smaller halves, sorts each half and combines the sorted halves with a merge.

Split [8,3,6,2] into [8,3] and [6,2], then into singletons. A singleton is already sorted. Merge8 and3 into [3,8]; merge6 and2 into [2,6]. To combine these, compare the next unused items: take2, then3, then6; append the remaining8, giving [2,3,6,8]. Never concatenate the sorted halves and assume the concatenation is sorted.

The following recursive method returns a sorted copy and leaves its input unchanged. It uses import java.util.Arrays; and a merge method which combines two ascending arrays. Length0 and1 are base cases, including unequal half lengths for an odd-sized input.

static int[] mergeSort(int[] a) {
    if (a.length <= 1) return a.clone();
    int mid = a.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
    return merge(left, right);
}