Merge sort

Merge sort is a divide-and-conquer sorting algorithm known for its efficiency. It recursively sorts sequences by breaking them down into trivially sorted single-element sequences, and then repeatedly merging sorted subsequences until there is only \(1\) sorted subsequence remaining, which is the sorted version of the original sequence.

Here's that beloved algorithm, merge_sort:

algorithm merge_sort is
    input: a sequence of n elements, S
    output: the sorted sequence

    if n = 1 (base case)
        return S
    else (recursive case)
        let L be a subsequence of S containing its first ⌈n / 2⌉ elements
        let R be a subsequence of S containing its last ⌊n / 2⌋ elements
        return merge(merge_sort(L), merge_sort(R))

Merge sort has an important subroutine called merge:

subroutine merge is
    input: 2 sequences, L and R
    output: the sorted sequence C created from merging L and R

    let C be an empty sequence
    while L and R are both not empty
        let l be the first element in L
        let r be the first element in R
        if l < r
            remove l from L and append it to C
        else
            remove r from R and append it to C
    append to C the elements of whichever sequence (L or R) is not empty, preserving order
    return C

With an impressive \(O(n \log n)\) time complexity, merge sort is one of the most efficient sorting algorithms out there.