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?"

Practice

1. What does the ORDER BY clause do in a MySQL query?

easy

A. It sorts the query results by one or more columns.

B. It filters rows based on a condition.

C. It groups rows with the same values.

D. It limits the number of rows returned.

Solution

1. Step 1: Understand the purpose of ORDER BY

   The ORDER BY clause is used to sort the results of a query based on one or more columns.

2. Step 2: Compare with other clauses

   Filtering rows is done by WHERE, grouping by GROUP BY, and limiting rows by LIMIT. So, only sorting matches ORDER BY.

3. Final Answer:

   It sorts the query results by one or more columns. -> Option A

4. Quick Check:

   ORDER BY = Sort results [OK]

Hint: ORDER BY sorts rows; WHERE filters rows [OK]

Common Mistakes:

• Confusing ORDER BY with WHERE clause
• Thinking ORDER BY filters rows
• Mixing ORDER BY with GROUP BY

2. Which of the following is the correct syntax to sort the table employees by the column salary in descending order?

easy

A. SELECT * FROM employees ORDER BY salary DOWN;

B. SELECT * FROM employees SORT BY salary DESC;

C. SELECT * FROM employees ORDER salary DESC;

D. SELECT * FROM employees ORDER BY salary DESC;

Solution

1. Step 1: Recall correct ORDER BY syntax

   The correct syntax to sort results is ORDER BY column_name ASC|DESC. Here, DESC means descending order.

2. Step 2: Check each option

   SELECT * FROM employees ORDER BY salary DESC; uses correct syntax. Options B, C, and D use invalid keywords or syntax.

3. Final Answer:

   SELECT * FROM employees ORDER BY salary DESC; -> Option D

4. Quick Check:

   ORDER BY + DESC = correct syntax [OK]

Hint: Use ORDER BY column DESC for descending sort [OK]

Common Mistakes:

• Using SORT BY instead of ORDER BY
• Omitting BY after ORDER
• Using DOWN instead of DESC

3. Given the table products with columns id and price, what will be the order of id after running this query?

SELECT id FROM products ORDER BY price ASC;

Assume the data:
id: 1, price: 50
id: 2, price: 20
id: 3, price: 30

medium

A. [1, 3, 2]

B. [2, 3, 1]

C. [3, 2, 1]

D. [1, 2, 3]

Solution

1. Step 1: Understand ORDER BY price ASC

   The query sorts rows by price in ascending order (lowest to highest).

2. Step 2: Sort the data by price

   Prices sorted ascending: 20 (id 2), 30 (id 3), 50 (id 1). So the id order is [2, 3, 1].

3. Final Answer:

   [2, 3, 1] -> Option B

4. Quick Check:

   Sort by price ASC = [2, 3, 1] [OK]

Hint: Sort by column values ascending to find order [OK]

Common Mistakes:

• Confusing ASC with DESC order
• Sorting by id instead of price
• Ignoring the ORDER BY clause

4. Identify the error in this query:

SELECT name FROM customers ORDER salary DESC;

medium

A. ORDER BY must come before SELECT

B. DESC cannot be used with ORDER

C. Missing BY keyword after ORDER

D. Missing WHERE clause

Solution

1. Step 1: Check ORDER BY syntax

   The correct syntax requires the keyword BY after ORDER. The query uses ORDER salary DESC which is invalid.

2. Step 2: Confirm other parts are correct

   DESC is valid with ORDER BY. No WHERE clause is needed for sorting. ORDER BY comes after SELECT.

3. Final Answer:

   Missing BY keyword after ORDER -> Option C

4. Quick Check:

   ORDER BY needs BY keyword [OK]

Hint: Always write ORDER BY, not just ORDER [OK]

Common Mistakes:

• Omitting BY after ORDER
• Using ORDER before SELECT
• Confusing DESC usage

5. You have a table students with columns name and score. You want to list all students sorted by their score from highest to lowest, but if two students have the same score, sort those students alphabetically by name ascending. Which query achieves this?

hard

A. SELECT * FROM students ORDER BY score DESC, name ASC;

B. SELECT * FROM students ORDER BY name ASC, score DESC;

C. SELECT * FROM students ORDER BY score ASC, name DESC;

D. SELECT * FROM students ORDER BY score DESC;

Solution

1. Step 1: Understand sorting requirements

   Primary sort is by score descending (highest first). Secondary sort for ties is by name ascending (alphabetical).

2. Step 2: Match query with requirements

   SELECT * FROM students ORDER BY score DESC, name ASC; orders by score DESC then name ASC, matching the requirement. SELECT * FROM students ORDER BY name ASC, score DESC; reverses order priorities. SELECT * FROM students ORDER BY score ASC, name DESC; sorts score ascending and name descending, which is wrong. SELECT * FROM students ORDER BY score DESC; misses secondary sort.

3. Final Answer:

   SELECT * FROM students ORDER BY score DESC, name ASC; -> Option A

4. Quick Check:

   ORDER BY score DESC, name ASC = correct [OK]

Hint: Use multiple columns in ORDER BY for tie-breakers [OK]

Common Mistakes:

• Reversing sort order priorities
• Missing secondary sort column
• Using ASC when DESC needed