ORDER BY single column in SQL - 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, the database needs to arrange rows in order. Understanding how the time to sort grows as the data grows helps us know how fast or slow queries might be.

We want to answer: How does sorting time change when 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 algorithm 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 a few more rows. Sorting usually takes more time than just reading rows one by one.

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

Pattern observation: When the number of rows grows 10 times, the sorting work grows roughly 10 times more than that, showing a faster growth than just linear.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes a bit more than just looking at each row once; it grows a little faster as the data grows bigger.

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 the time grows faster than just the number of rows.

Interview Connect

Knowing how sorting time grows helps you explain query performance clearly. It shows you understand how databases handle data and can help you write better queries or explain why some queries take longer.

Self-Check

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