ORDER BY single column in MySQL - Time & Space Complexity

Time Complexity: ORDER BY single column

O(n log n)

Understanding Time Complexity

When we sort data in a database using ORDER BY on one column, it takes some time depending on how much data there is.

We want to understand how the time to sort grows as the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
ORDER BY salary;
    

This query selects all employees and sorts them by their salary in ascending order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list of rows by the salary column.
• How many times: The sorting process compares and rearranges rows multiple times depending on the number of rows.

How Execution Grows With Input

As the number of rows increases, the sorting work grows faster than just adding more rows.

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

Pattern observation: The work grows faster than the number of rows, roughly multiplying by a bit more than the number of rows each time.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a bit faster than the number of rows, but not as fast as checking every pair of rows.

Common Mistake

[X] Wrong: "Sorting with ORDER BY takes the same time no matter how many rows there are."

[OK] Correct: Sorting needs to compare and rearrange rows, so more rows mean more work and more time.

Interview Connect

Understanding how sorting time grows helps you explain database performance clearly and shows you know how data size affects queries.

Self-Check

"What if we added an index on the salary column? How would the time complexity of ORDER BY change?"