Why ordering organizes results in MySQL - Performance Analysis

Time Complexity: Why ordering organizes results

O(n log n)

Understanding Time Complexity

When we ask a database to sort data, it takes some time to arrange the rows in order.

We want to understand how the time needed grows as the amount of data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
ORDER BY last_name ASC;

This query fetches all employees and sorts them by their last name in alphabetical order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list of employee rows by last_name.
• 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 employees grows, the sorting work grows faster than just counting 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 n each time.

Final Time Complexity

Time Complexity: O(n log n)

This means that if you double the number of rows, the sorting work grows a bit more than double, but not as fast as squaring.

Common Mistake

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

[OK] Correct: Sorting needs to compare and arrange rows, so more rows mean more work, not a fixed time.

Interview Connect

Understanding how sorting time grows helps you explain how databases handle ordering efficiently, a useful skill in many real tasks.

Self-Check

"What if we added an index on last_name? How would the time complexity of ordering change?"