np.sort() for sorting arrays in NumPy - Time & Space Complexity

Time Complexity: np.sort() for sorting arrays

O(n log n)

Understanding Time Complexity

When we sort data using np.sort(), we want to know how the time it takes changes as the data grows.

We ask: How much longer does sorting take if we double or triple the size of the array?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.random.randint(0, 1000, size=1000)
sorted_arr = np.sort(arr)

This code creates an array of 1000 random numbers and sorts it using np.sort().

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and swapping elements during sorting.
• How many times: Depends on the sorting algorithm, but generally many comparisons grow with array size.

How Execution Grows With Input

As the array size grows, the number of comparisons and moves grows faster than the size itself.

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

Pattern observation: Operations grow roughly a bit more than n times log n, which is faster than just n but slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means if you double the size of the array, sorting takes a bit more than double the time, but not as much as four times.

Common Mistake

[X] Wrong: "Sorting always takes time proportional to the square of the array size (O(n²))."

[OK] Correct: Modern sorting algorithms used by np.sort() are faster than simple methods like bubble sort and usually run in O(n log n) time, which is much quicker for large arrays.

Interview Connect

Knowing how sorting scales helps you understand performance in real tasks like organizing data or searching efficiently.

Self-Check

"What if we used np.sort() on a nearly sorted array? How would the time complexity change?"

Practice

1. What does the np.sort() function do when applied to a NumPy array?

easy

A. It returns a new array with elements sorted in ascending order.

B. It changes the original array to sorted order in place.

C. It reverses the order of elements in the array.

D. It removes duplicate elements from the array.

Solution

1. Step 1: Understand np.sort() behavior

   The np.sort() function returns a new sorted array and does not modify the original array.

2. Step 2: Identify the sorting order

   By default, np.sort() sorts elements in ascending order.

3. Final Answer:

   It returns a new array with elements sorted in ascending order. -> Option A

4. Quick Check:

   np.sort() returns sorted copy [OK]

Hint: np.sort() returns a new sorted array, original stays same [OK]

Common Mistakes:

• Thinking np.sort() sorts in place
• Confusing sorting with reversing
• Assuming it removes duplicates

2. Which of the following is the correct syntax to sort a 1D NumPy array named arr using np.sort()?

easy

A. np.sort(arr)

B. arr.sort()

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

D. arr.sorted()

Solution

1. Step 1: Recall np.sort() syntax

   The correct way to sort an array using the function is np.sort(arr).

2. Step 2: Check other options

   arr.sort() sorts in place but is a method, not np.sort(). np.sort(arr, axis=1) is invalid for 1D arrays. arr.sorted() is not a valid method.

3. Final Answer:

   np.sort(arr) -> Option A

4. Quick Check:

   np.sort(arr) is correct syntax [OK]

Hint: Use np.sort(array) to get sorted copy [OK]

Common Mistakes:

• Using arr.sorted() which does not exist
• Using axis=1 on 1D array
• Confusing np.sort() with arr.sort() method

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=1)
print(sorted_arr)

medium

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

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

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

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

Solution

1. Step 1: Understand sorting along axis=1

   Sorting with axis=1 sorts each row independently in ascending order.

2. Step 2: Sort each row

   First row [3,1,2] sorted is [1,2,3]. Second row [6,4,5] sorted is [4,5,6].

3. Final Answer:

   [[1 2 3] [4 5 6]] -> Option C

4. Quick Check:

   Row-wise sort = [[1 2 3], [4 5 6]] [OK]

Hint: axis=1 sorts each row separately [OK]

Common Mistakes:

• Sorting columns instead of rows
• Expecting original array unchanged in print
• Confusing axis parameter meaning

4. The following code throws an error. What is the cause?

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

medium

A. np.sort() cannot sort integer arrays.

B. Missing parentheses in np.sort call.

C. The array must be converted to a list first.

D. Axis 1 does not exist for 1D arrays.

Solution

1. Step 1: Check array dimensions

   The array arr is 1D, so it only has axis 0.

2. Step 2: Understand axis parameter

   Using axis=1 on a 1D array causes an error because axis 1 does not exist.

3. Final Answer:

   Axis 1 does not exist for 1D arrays. -> Option D

4. Quick Check:

   1D array has only axis 0 [OK]

Hint: 1D arrays only have axis=0, axis=1 causes error [OK]

Common Mistakes:

• Assuming axis=1 works on 1D arrays
• Thinking np.sort can't handle integers
• Believing array must be list to sort

5. Given a 2D NumPy array data = np.array([[7, 2, 9], [4, 5, 1], [8, 3, 6]]), how can you sort the entire array as if it were a flat list, then reshape it back to the original shape?

hard

A. np.sort(data, axis=0).reshape(data.shape)

B. np.sort(data, axis=None).reshape(data.shape)

C. data.sort(axis=1).reshape(data.shape)

D. np.sort(data).reshape(data.shape)

Solution

1. Step 1: Flatten and sort the entire array

   Using axis=None in np.sort() sorts the array as a flat 1D array.

2. Step 2: Reshape sorted array back to original shape

   Use .reshape(data.shape) to restore the 2D shape after sorting.

3. Final Answer:

   np.sort(data, axis=None).reshape(data.shape) -> Option B

4. Quick Check:

   axis=None sorts flat, reshape restores shape [OK]

Hint: Use axis=None to sort flat, then reshape [OK]

Common Mistakes:

• Sorting only rows or columns instead of flat
• Using data.sort() which sorts in place
• Omitting reshape after sorting flat