4.3.5.1–4.3.5.2 - Bubble sort and merge sort (C#)

Bubble passes and swaps

Bubble sort repeatedly compares adjacent elements and swaps a pair that is in the wrong order. In an ascending left-to-right pass, a large element moves right through successive swaps; after a full pass the largest remaining element is in its final position.

For [7, 2, 5, 1], the first pass compares 7/2 → [2, 7, 5, 1], then 7/5 → [2, 5, 7, 1], then 7/1 → [2, 5, 1, 7]. The next pass need not compare the final 7: 2/5 needs no swap, then 5/1 gives [2, 1, 5, 7]. The third pass gives [1, 2, 5, 7].

This complete static C# method sorts its argument in place and stops early when a pass makes no swaps.

class Program
{
    static void BubbleSort(int[] values)
    {
        for (int end = values.Length - 1; end > 0; end--)
        {
            bool swapped = false;
            for (int i = 0; i < end; i++)
                if (values[i] > values[i + 1])
                {
                    int temp = values[i];
                    values[i] = values[i + 1];
                    values[i + 1] = temp;
                    swapped = true;
                }
            if (!swapped) break;
        }
    }
}

The temporary variable preserves the old left element. Assigning both elements without preserving it would duplicate a value and lose another. The comparison is strictly >: equal elements need not be swapped. Empty and singleton arrays require no pass.

In the worst case the inner comparisons number $(n-1)+(n-2)+\cdots+1 = n(n-1)/2$, giving $O(n^2)$ time. The optimized method makes only one pass on an already sorted array, so its best case is $O(n)$. A version without early stopping still makes quadratic comparisons on sorted input. State the version before claiming its best case.

Merge and divide-and-conquer

Merge sort uses divide and conquer: split the collection into smaller subproblems, sort those subproblems, then combine their sorted results. A collection of zero or one item is already sorted, providing the recursive base case.

For [8, 3, 6, 2], split into [8, 3] and [6, 2], then four singleton lists. Merge [8] and [3] into [3, 8]; merge [6] and [2] into [2, 6]; then merge those into [2, 3, 6, 8]. To merge, compare the first unconsumed items, take the smaller, and advance only that input's position. When one input is exhausted, copy the remainder of the other.