Sorting by index in Pandas - Time & Space Complexity

Time Complexity: Sorting by index

O(n log n)

Understanding Time Complexity

When we sort data by its index in pandas, we want to know how the time it takes changes as the data grows.

We ask: How does sorting by index get slower or faster when we have more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

df = pd.DataFrame({
    'value': [5, 3, 6, 2, 8]
}, index=[4, 2, 5, 1, 3])

sorted_df = df.sort_index()
print(sorted_df)

This code creates a small table with an unordered index and sorts it by that index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and swapping index values to order them.
• How many times: The sorting algorithm compares pairs of index entries multiple times, depending on the number of rows.

How Execution Grows With Input

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

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

Pattern observation: The work grows faster than the number of rows, roughly like rows times the log of rows.

Final Time Complexity

Time Complexity: O(n log n)

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

Common Mistake

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

[OK] Correct: Sorting needs to compare many pairs of rows, so more rows mean more comparisons and more time.

Interview Connect

Understanding how sorting scales helps you explain how data operations behave as data grows, a useful skill in many data tasks.

Self-Check

"What if the index was already sorted? How would the time complexity change when sorting by index?"

Practice

1. What does sorting by index in pandas do?

easy

A. It changes the data values to alphabetical order.

B. It filters rows based on a condition.

C. It removes duplicate rows from the DataFrame.

D. It arranges data rows or columns based on their labels.

Solution

1. Step 1: Understand the meaning of sorting by index

   Sorting by index means arranging the data based on the row or column labels, not the data values.

2. Step 2: Compare options with the definition

   Only It arranges data rows or columns based on their labels. correctly describes sorting by index as arranging rows or columns by their labels.

3. Final Answer:

   It arranges data rows or columns based on their labels. -> Option D

4. Quick Check:

   Sorting by index = arrange by labels [OK]

Hint: Sorting by index means ordering by labels, not values [OK]

Common Mistakes:

• Confusing sorting by index with sorting by values
• Thinking it filters or removes data
• Assuming it changes data values

2. Which of the following is the correct syntax to sort a DataFrame df by its row index in descending order without changing the original DataFrame?

easy

A. df.sort_index(ascending=False, inplace=False)

B. df.sort_index(axis=1, ascending=False)

C. df.sort_index(ascending=True, inplace=False)

D. df.sort_index(ascending=False, inplace=True)

Solution

1. Step 1: Identify parameters for sorting by index

   To sort by row index descending, use ascending=False. To avoid changing original, use inplace=False.

2. Step 2: Check each option

   df.sort_index(ascending=False, inplace=False) uses ascending=False and inplace=False, which matches the requirement. df.sort_index(ascending=False, inplace=True) changes original (inplace=True). df.sort_index(ascending=True, inplace=False) sorts ascending. df.sort_index(axis=1, ascending=False) sorts columns (axis=1).

3. Final Answer:

   df.sort_index(ascending=False, inplace=False) -> Option A

4. Quick Check:

   Descending + no inplace = ascending=False, inplace=False [OK]

Hint: Use inplace=False to keep original unchanged [OK]

Common Mistakes:

• Using inplace=True when original should not change
• Confusing ascending=True with descending order
• Sorting columns instead of rows by mistake

3. Given the DataFrame df with index labels [3, 1, 2] and values ["a", "b", "c"], what will df.sort_index() return as the index order?

medium

A. [a, b, c]

B. [1, 2, 3]

C. [3, 2, 1]

D. [c, b, a]

Solution

1. Step 1: Understand default sort_index behavior

   By default, sort_index sorts row labels in ascending order.

2. Step 2: Apply sorting to index [3, 1, 2]

   Sorting ascending gives [1, 2, 3]. Values remain associated with their labels.

3. Final Answer:

   [1, 2, 3] -> Option B

4. Quick Check:

   Default sort_index sorts index ascending [OK]

Hint: Default sort_index sorts index ascending [OK]

Common Mistakes:

• Confusing index labels with values
• Assuming sort_index sorts values instead of index
• Thinking sort_index reverses order by default

4. You run df.sort_index(axis=2) on a DataFrame but get an error. What is the likely cause?

medium

A. axis=2 is invalid; axis must be 0 or 1.

B. sort_index does not accept axis parameter.

C. DataFrame index labels are missing.

D. inplace parameter is required.

Solution

1. Step 1: Check valid axis values for sort_index

   sort_index accepts axis=0 (rows) or axis=1 (columns) only.

2. Step 2: Identify error cause with axis=2

   axis=2 is invalid and causes an error.

3. Final Answer:

   axis=2 is invalid; axis must be 0 or 1. -> Option A

4. Quick Check:

   axis must be 0 or 1 in sort_index [OK]

Hint: axis can only be 0 (rows) or 1 (columns) [OK]

Common Mistakes:

• Using axis values other than 0 or 1
• Assuming sort_index ignores invalid axis
• Forgetting axis parameter is optional but must be valid

5. You have a DataFrame df with a multi-level index (two levels). How do you sort df by the second level of the index in ascending order without changing the original DataFrame?

hard

A. df.sort_values(level=1, ascending=True)

B. df.sort_index(level=0, ascending=True, inplace=True)

C. df.sort_index(level=1, ascending=True, inplace=False)

D. df.sort_index(axis=1, level=1)

Solution

1. Step 1: Understand sorting multi-level index

   Use sort_index with level parameter to specify which index level to sort.

2. Step 2: Choose correct parameters

   To sort by second level (level=1), ascending order, and keep original unchanged, use inplace=False.

3. Final Answer:

   df.sort_index(level=1, ascending=True, inplace=False) -> Option C

4. Quick Check:

   Sort multi-level index by level=1, inplace=False [OK]

Hint: Use level parameter to sort multi-level index [OK]

Common Mistakes:

• Using sort_values instead of sort_index for index sorting
• Sorting wrong index level (level=0 instead of 1)
• Using inplace=True when original should not change