Sorting along axes in NumPy - Time & Space Complexity

Time Complexity: Sorting along axes

O(n * m log m)

Understanding Time Complexity

Sorting data is common in data science to organize information. When sorting along an axis in numpy, we want to know how the time needed grows as the data size grows.

We ask: How does sorting time change when we have bigger arrays or sort along different axes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.random.rand(1000, 1000)
sorted_arr = np.sort(arr, axis=1)

This code creates a 1000x1000 array of random numbers and sorts each row independently.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting each row of the 2D array.
• How many times: Sorting is done once per row, so 1000 times for 1000 rows.

How Execution Grows With Input

Sorting each row takes time depending on the row length. Doing this for all rows adds up.

Input Size (n x m)	Approx. Operations
10 x 10	10 rows x sorting 10 items each ≈ 10 x 10 log 10
100 x 100	100 rows x sorting 100 items each ≈ 100 x 100 log 100
1000 x 1000	1000 rows x sorting 1000 items each ≈ 1000 x 1000 log 1000

Pattern observation: The time grows roughly with the number of rows times the sorting cost per row, which depends on the row length times its logarithm.

Final Time Complexity

Time Complexity: O(n * m log m)

This means sorting each of the n rows of length m takes time proportional to n times m log m.

Common Mistake

[X] Wrong: "Sorting the whole 2D array is just O(n log n) because it's one big sort."

[OK] Correct: Sorting along an axis sorts each row separately, so the time depends on sorting each row, not the whole array as one list.

Interview Connect

Understanding how sorting time grows with data size helps you explain performance in real tasks. It shows you can think about how algorithms work on multi-dimensional data.

Self-Check

"What if we sorted along axis=0 (columns) instead of axis=1? How would the time complexity change?"

Practice

1. What does the axis parameter control in numpy.sort?

easy

A. It decides whether to sort rows or columns in an array.

B. It sets the sorting algorithm type.

C. It changes the data type of the array before sorting.

D. It specifies the order of sorting (ascending or descending).

Solution

1. Step 1: Understand the role of axis in sorting

   The axis parameter tells numpy which direction to sort: 0 means sort each column, 1 means sort each row.

2. Step 2: Differentiate from other parameters

   Sorting algorithm type and order are controlled by other parameters, not axis.

3. Final Answer:

   It decides whether to sort rows or columns in an array. -> Option A

4. Quick Check:

   axis controls direction = A [OK]

Hint: Remember axis=0 sorts columns, axis=1 sorts rows [OK]

Common Mistakes:

• Confusing axis with sorting order
• Thinking axis changes data type
• Assuming axis sets sorting algorithm

2. Which of the following is the correct syntax to sort a 2D numpy array arr along rows?

easy

A. numpy.sort(arr, axis=0)

B. numpy.sort(arr, axis=None)

C. numpy.sort(arr, axis=1)

D. numpy.sort(arr, axis=2)

Solution

1. Step 1: Identify axis for sorting rows

   In a 2D array, axis=1 means sorting each row individually.

2. Step 2: Check other options for validity

   Axis=0 sorts columns, axis=None flattens the array into 1D before sorting, axis=2 is invalid for 2D arrays.

3. Final Answer:

   numpy.sort(arr, axis=1) -> Option C

4. Quick Check:

   axis=1 sorts rows = B [OK]

Hint: Use axis=1 to sort rows in 2D arrays [OK]

Common Mistakes:

• Using axis=0 to sort rows
• Using invalid axis like 2 for 2D arrays
• Using axis=None which flattens the array

3. What is the output of the following code?

import numpy as np
arr = np.array([[3, 1, 2], [6, 4, 5]])
sorted_arr = np.sort(arr, axis=0)
print(sorted_arr)

medium

A. [[1 2 3]
[4 5 6]]

B. [[3 1 2]
[6 4 5]] sorted by columns

C. [[3 1 2]
[6 4 5]] (unchanged)

D. [[3 1 2]
[6 4 5]]

Solution

1. Step 1: Understand sorting along axis=0

   Sorting with axis=0 sorts each column independently in ascending order.

2. Step 2: Sort each column of the array

   Columns: [3,6] -> [3,6], [1,4] -> [1,4], [2,5] -> [2,5]. Since columns are already sorted, array remains the same.

3. Final Answer:

   [[3 1 2] [6 4 5]] sorted by columns -> Option B

4. Quick Check:

   axis=0 sorts columns = A [OK]

Hint: axis=0 sorts columns top to bottom [OK]

Common Mistakes:

• Assuming sorting rearranges rows
• Confusing axis=0 with axis=1
• Expecting full array sort instead of column-wise

4. The code below throws an error. What is the problem?

import numpy as np
arr = np.array([[1, 3], [2, 4]])
sorted_arr = np.sort(arr, axis=2)
print(sorted_arr)

medium

A. Axis 2 does not exist for a 2D array.

B. The array contains non-numeric data.

C. The sort function requires axis to be None.

D. The array must be 1D to sort.

Solution

1. Step 1: Check array dimensions

   The array is 2D with shape (2,2), so valid axes are 0 and 1 only.

2. Step 2: Validate axis parameter

   Using axis=2 is invalid and causes an IndexError because axis 2 does not exist.

3. Final Answer:

   Axis 2 does not exist for a 2D array. -> Option A

4. Quick Check:

   Axis must be within array dimensions = C [OK]

Hint: Axis must be less than array dimensions [OK]

Common Mistakes:

• Using axis out of range
• Assuming sort only works on 1D arrays
• Confusing axis with array shape

5. Given a 3D numpy array arr with shape (2, 2, 3), how would you sort the array along the last axis for each 2D slice?

hard

A. np.sort(arr, axis=-2)

B. np.sort(arr, axis=1)

C. np.sort(arr, axis=0)

D. np.sort(arr, axis=2)

Solution

1. Step 1: Identify the last axis in a 3D array

   For shape (2, 2, 3), axes are 0, 1, 2. The last axis is 2.

2. Step 2: Use axis=2 to sort along the last axis

   Sorting with axis=2 sorts each 2D slice along the last dimension (length 3).

3. Final Answer:

   np.sort(arr, axis=2) -> Option D

4. Quick Check:

   Last axis is 2, so axis=2 sorts last dimension [OK]

Hint: Use axis=-1 or axis=2 for last axis in 3D arrays [OK]

Common Mistakes:

• Using axis=0 or 1 instead of last axis
• Confusing negative axis indexing
• Not matching axis to array shape