sort_index() for index sorting in Pandas - Time & Space Complexity

Time Complexity: sort_index() for index sorting

O(n log n)

Understanding Time Complexity

When we sort data by its index using pandas, it takes some time depending on how much data there is.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

df = pd.DataFrame({
    'value': [10, 20, 30, 40]
}, index=[3, 1, 4, 2])

sorted_df = df.sort_index()

This code creates a small table with an unsorted index and then sorts the table by that index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting algorithm compares and rearranges index values.
• How many times: It processes each index value multiple times depending on the sorting method.

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 operations
100	About 700 to 800 operations
1000	About 10,000 to 12,000 operations

Pattern observation: The operations grow faster than the input size, roughly multiplying by a bit more than the input size each time.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as data grows, but not as fast as checking every pair; it grows in a balanced way.

Common Mistake

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

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

Interview Connect

Understanding how sorting scales helps you explain how data operations behave in real projects, showing you know how to handle growing data efficiently.

Self-Check

"What if the index was already sorted? How would the time complexity change when using sort_index()?"