Sorted and custom comparators in Swift - Time & Space Complexity

Time Complexity: Sorted and custom comparators

O(n log n)

Understanding Time Complexity

When we sort items using Swift's sorted method with a custom comparator, we want to know how the time it takes changes as the list grows.

We ask: How does sorting time grow when we have more items to sort?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let numbers = [5, 3, 8, 1, 2]
let sortedNumbers = numbers.sorted { a, b in
    return a < b
}
print(sortedNumbers)
    

This code sorts an array of numbers in ascending order using a custom comparison closure.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting algorithm repeatedly compares pairs of elements using the custom comparator.
• How many times: The number of comparisons grows as the sorting algorithm processes the list, depending on the sorting method used internally.

How Execution Grows With Input

As the list gets bigger, the number of comparisons needed to sort grows faster than the list size itself.

Input Size (n)	Approx. Operations
10	About 30 comparisons
100	About 700 comparisons
1000	About 10,000 comparisons

Pattern observation: The number of operations grows roughly like n log n, meaning doubling the list size makes the work about twice as much (plus a bit more).

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as the list grows, but not as fast as checking every pair; it grows a bit faster than just the list size.

Common Mistake

[X] Wrong: "Sorting with a custom comparator always takes longer than sorting with default methods."

[OK] Correct: The custom comparator only changes how two items are compared, not the overall sorting method. The time mainly depends on the number of items, not the comparator itself.

Interview Connect

Understanding how sorting time grows helps you explain your code choices clearly and shows you know how to handle data efficiently in real projects.

Self-Check

What if we changed the custom comparator to sort in descending order? How would the time complexity change?