I once worked with a developer who had implemented a nested loop to sort a list of a few hundred financial transactions in a fintech app. On his high-end MacBook Pro using the simulator, it felt instantaneous. But when the app hit the hands of a user on a five-year-old iPhone with a few thousand transactions? The UI thread just hung. He hadn't realized he'd accidentally written a Bubble Sort, and the $O(n^2)$ complexity had finally caught up with him. While Swift's built-in .sort() is incredibly optimized (it uses a hybrid algorithm called Timsort), there are times—whether it's a technical interview, a specialized memory constraint, or building a sorting visualizer—where you need to implement these yourself.

The Naive Approach and Why It Fails

If you're just starting to think about sorting, you'll likely land on Bubble Sort. It's intuitive: you walk through the list, compare adjacent elements, and swap them if they're in the wrong order. You keep doing this until the largest element "bubbles" up to the end. It's simple to write, but it's devastatingly slow for large datasets.

func bubbleSort<T: Comparable>(_ array: inout [T]) {
    let n = array.count
    for i in 0<n {
        for j in 0<(n - i - 1) {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
            }
        }
    }
}

I usually tell people to treat Bubble Sort as a cautionary tale. The nested loops mean that if you double your input size, the work doesn't double—it quadruples. In a professional environment, if I see this in a PR, I'm going to ask why it's there unless we're dealing with a list of maybe five items where simplicity outweighs performance.

Efficiency Through Divide and Conquer

To get real performance, we have to stop looking at the list as one big block and start breaking it down. Quick Sort is the gold standard here. It picks a "pivot" element and partitions the rest of the array into two groups: those smaller than the pivot and those larger. Then, it recursively sorts those subgroups. I prefer the "Hoare partition scheme" for its efficiency, but for clarity, let's look at a more readable Swift implementation using generics.

func quickSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    
    let pivot = array[array.count / 2]
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }
    
    return quickSort(less) + equal + quickSort(greater)
}

Now, the version above is elegant and very "Swifty," but it allocates a lot of new arrays. In a high-performance system, you'd do this "in-place" using indices to avoid hitting the heap constantly. Still, the logic remains: by splitting the problem in half repeatedly, we move from $O(n^2)$ to $O(n \log n)$, which is a massive leap in speed.

Predictability and Stability with Merge Sort

Quick Sort is fast, but it has a weakness: if you pick a bad pivot on an already sorted list, it can still degrade to $O(n^2)$. If you need a guarantee that the sort will always perform consistently regardless of the input order, Merge Sort is your best bet. It's also "stable," meaning if two elements are equal, they keep their original relative order—something that's crucial if you're sorting a list of users by "Last Name," and then sorting that resulting list by "City."

func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    
    let middle = array.count / 2
    let left = mergeSort(Array(array[0...middle-1]))
    let right = mergeSort(Array(array[middle...]))
    
    return merge(left, right)
}

func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
    var leftIndex = 0
    var rightIndex = 0
    var orderedArray: [T] = []
    
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            orderedArray.append(left[leftIndex])
            leftIndex += 1
        } else {
            orderedArray.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    return orderedArray + Array(left[leftIndex...]) + Array(right[rightIndex...])
}

You'll notice Merge Sort uses more memory than Quick Sort because it creates these temporary arrays during the merge phase. It's a classic engineering trade-off: you're spending memory to buy yourself a guarantee of stability and consistent time complexity.

📋 Practical Task

Implementing a High-Score Leaderboard Sorter

You are building a game leaderboard. You have a Player struct with a name (String) and a score (Int). The requirements are as follows:

• Implement a Quick Sort function that sorts the players in descending order (highest score first).
• Implement a Merge Sort function that sorts the players in ascending order (lowest score first).
• Ensure both functions are generic enough to work with any Player array.

Starter Code:

struct Player {
    let name: String
    let score: Int
}

var players = [
    Player(name: "Alice", score: 450),
    Player(name: "Bob", score: 1200),
    Player(name: "Charlie", score: 800),
    Player(name: "Diana", score: 1200),
    Player(name: "Eve", score: 300)
]

Goal: Write the two sorting functions and test them. When using Merge Sort on the players array, verify that "Bob" and "Diana" (who both have 1200 points) maintain their relative order from the original array.