Bubble Sort

Bubble sort repeatedly steps through the list, comparing adjacent elements and swapping them if they're in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the end.

Algorithm

function bubbleSort(arr)
    n ← len(arr)
    for i ← 0 to n - 2        // n-1 passes
        swapped ← false
        for j ← 0 to n - 2 - i  // inner loop shrinks each pass
            if arr[j] > arr[j+1] then
                swap arr[j] and arr[j+1]
                swapped ← true
            endif
        next j
        if swapped = false then break  // early exit if sorted
    next i
    return arr
endfunction

Worked Example

Sort: [5, 3, 8, 1, 4]

Complexity

Stable: Yes — equal elements maintain relative order (swaps only when strictly greater). In-place: Yes — O(1) extra space.

Insertion Sort

Insertion sort builds a sorted portion one element at a time. It takes each element from the unsorted portion and inserts it into its correct position in the sorted portion — like sorting a hand of playing cards.

Algorithm

function insertionSort(arr)
    for i ← 1 to len(arr) - 1
        key ← arr[i]       // element to insert
        j ← i - 1
        while j >= 0 AND arr[j] > key
            arr[j+1] ← arr[j]   // shift right to make space
            j ← j - 1
        endwhile
        arr[j+1] ← key    // insert key in correct position
    next i
    return arr
endfunction

Worked Example

Sort: [5, 2, 4, 6, 1, 3] — sorted portion shown in bold

Complexity

Stable: Yes. In-place: Yes — O(1) extra space. Best sorting algorithm for nearly-sorted data and online sorting (receiving elements one at a time).

Merge Sort

Merge sort is a divide-and-conquer algorithm. It recursively divides the list in half until single elements remain, then merges the halves back together in sorted order.

Phase 1: Divide

function mergeSort(arr)
    if len(arr) <= 1 then return arr    // base case
    mid ← len(arr) DIV 2
    left ← mergeSort(arr[0..mid-1])    // recursive call
    right ← mergeSort(arr[mid..end])   // recursive call
    return merge(left, right)
endfunction

Phase 2: Merge (the key step)

function merge(left, right)
    result ← []
    i ← 0; j ← 0
    while i < len(left) AND j < len(right)
        if left[i] <= right[j] then
            result.append(left[i]); i ← i + 1
        else
            result.append(right[j]); j ← j + 1
        endif
    endwhile
    // append remaining elements
    while i < len(left): result.append(left[i]); i ← i + 1
    while j < len(right): result.append(right[j]); j ← j + 1
    return result
endfunction

Worked Example

Sort: [5, 3, 8, 1, 4, 2]

Divide:         [5, 3, 8, 1, 4, 2]
             [5, 3, 8]    [1, 4, 2]
           [5,3] [8]    [1,4] [2]
           [5][3]        [1][4]

Conquer (merge up):
[5][3] → [3,5]     [1][4] → [1,4]
[3,5][8] → [3,5,8] [1,4][2] → [1,2,4]
[3,5,8] + [1,2,4] → [1,2,3,4,5,8]

Complexity

Stable: Yes (use ≤ in merge comparison). Not in-place: O(n) extra space for temporary arrays during merging. The O(n log n) in ALL cases is merge sort's key advantage.

Comparison Table