Sort_by for custom sorting in Ruby - Time & Space Complexity

Time Complexity: Sort_by for custom sorting

O(n log n)

Understanding Time Complexity

When we use sort_by in Ruby, it helps us sort items based on a custom rule.

We want to know how the time it takes to sort grows as we have more items.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

items = ["apple", "banana", "pear", "grape"]
sorted = items.sort_by { |item| item.length }
puts sorted

This code sorts a list of words by their length using sort_by.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting process compares items based on their length.
• How many times: It compares items multiple times, roughly proportional to the number of items times the logarithm of that number.

How Execution Grows With Input

As the list gets bigger, the number of comparisons grows faster than just the number of items.

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

Pattern observation: The work grows a bit faster than the list size, but not as fast as the square of the size.

Final Time Complexity

Time Complexity: O(n log n)

This means that if you double the number of items, the time to sort grows a bit more than double, but much less than square.

Common Mistake

[X] Wrong: "Sorting with sort_by takes the same time no matter how many items there are."

[OK] Correct: Sorting needs to compare items, and more items mean more comparisons, so time grows as the list grows.

Interview Connect

Understanding how sorting time grows helps you explain your code choices clearly and shows you know how your program behaves with bigger data.

Self-Check

"What if the block inside sort_by was more complex and took longer to run for each item? How would that affect the time complexity?"