Sort an Array
MedPrompt
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessarily unique.
Constraints:
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
Approaches
4 approaches with complexity analysis and trade-offs.
Bubble Sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The passes through the list are repeated until the list is sorted. While simple to understand, its performance is poor for large datasets, making it impractical for this problem's constraints.
Algorithm
- Iterate from
i = 0ton-2. - In an inner loop, iterate from
j = 0ton-i-2. - Compare
nums[j]withnums[j+1]. - If
nums[j] > nums[j+1], swap them. - After each outer loop iteration, the i-th largest element is placed at its correct position.
Walkthrough
The algorithm works by making multiple passes through the array. In each pass, it compares each pair of adjacent items and swaps them if they are in the wrong order. This process effectively "bubbles" the largest unsorted element up to its correct position at the end of the array. An optimization can be made: if a complete pass is made without any swaps, the array is already sorted, and the algorithm can terminate early.
class Solution { public int[] sortArray(int[] nums) { int n = nums.length; boolean swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { if (nums[j] > nums[j + 1]) { // swap nums[j] and nums[j+1] int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; swapped = true; } } // If no two elements were swapped by inner loop, then break if (!swapped) { break; } } return nums; }}Complexity
Time
`O(n^2)` - In the worst and average cases, there are two nested loops, leading to a quadratic time complexity. The best case is `O(n)` if the array is already sorted and the optimization is used.
Space
`O(1)` - The sort is performed in-place, requiring only a constant amount of extra space for a temporary variable during swaps.
Trade-offs
Pros
Simple to understand and implement.
Space efficient (
O(1)).
Cons
Highly inefficient for large arrays, with a time complexity of
O(n^2).Fails to meet the
O(n log n)time complexity requirement of the problem.
Quick Sort is a highly efficient, divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. While its average-case performance is excellent, its worst-case performance is O(n^2), which does not satisfy the problem's strict time complexity requirement.
Algorithm
- Define a recursive function
quickSort(arr, low, high). - The base case for the recursion is
low >= high. - Choose a pivot element. A common strategy is to pick the last element, or a random element to avoid worst-case scenarios.
- Partition the array around the pivot. All elements smaller than the pivot are moved to its left, and all greater elements to its right. Let the pivot's final index be
pi. - Recursively call
quickSort(arr, low, pi - 1). - Recursively call
quickSort(arr, pi + 1, high).
Walkthrough
The key to Quick Sort is the partition() function. This function takes an array and a pivot element, and rearranges the array such that all elements smaller than the pivot are on its left, and all elements greater are on its right. The pivot is then in its final sorted position. This process is applied recursively to the sub-arrays. The choice of pivot is crucial; a poor choice (like always picking the first or last element in an already sorted array) leads to the O(n^2) worst case. Randomizing the pivot choice can help avoid this. The implementation below uses the Lomuto partition scheme with a randomized pivot to improve performance.
import java.util.Random; class Solution { public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } private void quickSort(int[] nums, int low, int high) { if (low < high) { int pi = partition(nums, low, high); quickSort(nums, low, pi - 1); quickSort(nums, pi + 1, high); } } private int partition(int[] nums, int low, int high) { Random rand = new Random(); int pivotIndex = low + rand.nextInt(high - low + 1); swap(nums, pivotIndex, high); int pivot = nums[high]; int i = (low - 1); for (int j = low; j < high; j++) { if (nums[j] < pivot) { i++; swap(nums, i, j); } } swap(nums, i + 1, high); return i + 1; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Complexity
Time
`O(n log n)` on average. The partitioning takes `O(n)` time. If the pivot consistently divides the array into two roughly equal halves, the recursion depth is `O(log n)`. The worst-case complexity is `O(n^2)` if the pivot choices are consistently poor.
Space
`O(log n)` on average for the recursion call stack. The worst-case space complexity is `O(n)`.
Trade-offs
Pros
Very fast in practice, often outperforming other
O(n log n)algorithms.In-place sorting (Lomuto partition scheme), leading to low space overhead (
O(log n)).
Cons
Worst-case time complexity is
O(n^2), which violates the problem's requirement.Not a stable sort (the relative order of equal elements may change).
Merge Sort is a classic divide-and-conquer algorithm that guarantees an O(n log n) runtime. It works by recursively dividing the array into halves until each sub-array contains a single element, and then merges these sub-arrays back together in sorted order.
Algorithm
- Define a recursive function
mergeSort(arr, left, right). - The base case is
left >= right. - Find the middle point:
mid = (left + right) / 2. - Recursively call
mergeSort(arr, left, mid). - Recursively call
mergeSort(arr, mid + 1, right). - Call a
merge(arr, left, mid, right)function to merge the two sorted halves.
Walkthrough
The algorithm has two main parts: the recursive division and the merging.
- Divide: The
mergeSortfunction recursively splits the array in half until it can no longer be divided (i.e., the sub-array has 0 or 1 elements, which is inherently sorted). - Merge: The
mergefunction is the core of the algorithm. It takes two sorted sub-arrays and combines them into a single sorted array. It does this by creating temporary arrays to hold the sub-arrays and then iteratively comparing the elements of the temporary arrays, placing the smaller element into the original array. This merging step requires extra space.
class Solution { public int[] sortArray(int[] nums) { if (nums == null || nums.length <= 1) { return nums; } int[] temp = new int[nums.length]; mergeSort(nums, temp, 0, nums.length - 1); return nums; } private void mergeSort(int[] nums, int[] temp, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(nums, temp, left, mid); mergeSort(nums, temp, mid + 1, right); merge(nums, temp, left, mid, right); } } private void merge(int[] nums, int[] temp, int left, int mid, int right) { for (int i = left; i <= right; i++) { temp[i] = nums[i]; } int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (temp[i] <= temp[j]) { nums[k++] = temp[i++]; } else { nums[k++] = temp[j++]; } } while (i <= mid) { nums[k++] = temp[i++]; } }}Complexity
Time
`O(n log n)` - The recurrence relation is T(n) = 2T(n/2) + O(n), which resolves to `O(n log n)`. This holds for the worst, average, and best cases.
Space
`O(n)` - The `merge` step requires an auxiliary array of the same size as the input array to store the elements while merging.
Trade-offs
Pros
Guaranteed
O(n log n)time complexity, making it reliable.It is a stable sort.
Cons
Requires
O(n)extra space, which can be a significant drawback for very large arrays or in memory-constrained environments. It does not meet the "smallest space complexity" part of the problem's requirement.
Heap Sort is an efficient, in-place sorting algorithm that leverages a binary heap data structure. It meets both the O(n log n) time complexity and the minimal space complexity requirements of the problem, making it an optimal solution.
Algorithm
- Build a max heap from the input array. This is done by calling a
heapifyfunction for all non-leaf nodes, starting from the last one and moving up to the root. - Loop from
i = n-1down to1:- Swap the root of the heap (
nums[0]) with the current last element (nums[i]) - Reduce the considered heap size by one.
- Call
heapifyon the root (index 0) to restore the max heap property for the reduced heap.
- Swap the root of the heap (
- The array is now sorted.
Walkthrough
The algorithm consists of two main phases:
- Heapify Phase: The input array is converted into a max heap. A max heap is a complete binary tree where the value of each node is greater than or equal to the values of its children. This can be done efficiently in
O(n)time by starting from the last non-leaf node and repeatedly calling aheapifyfunction to satisfy the heap property. - Sortdown Phase: The largest element is at the root of the max heap. It is swapped with the last element of the heap (the end of the array), and the heap size is reduced by one. The
heapifyfunction is then called on the root to restore the max heap property. This process of swapping and heapifying is repeated until the heap is empty, resulting in a sorted array.
class Solution { public int[] sortArray(int[] nums) { int n = nums.length; // Build max heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) { heapify(nums, n, i); } // One by one extract an element from heap for (int i = n - 1; i > 0; i--) { // Move current root to end int temp = nums[0]; nums[0] = nums[i]; nums[i] = temp; // call max heapify on the reduced heap heapify(nums, i, 0); } return nums; } void heapify(int[] nums, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && nums[left] > nums[largest]) { largest = left; } if (right < n && nums[right] > nums[largest]) { largest = right; } if (largest != i) { int swap = nums[i]; nums[i] = nums[largest]; nums[largest] = swap; // Recursively heapify the affected sub-tree heapify(nums, n, largest); } }}Complexity
Time
`O(n log n)` - Building the initial heap takes `O(n)` time. Then, `n-1` elements are extracted from the heap. Each extraction involves a swap and a `heapify` operation, which takes `O(log k)` time where `k` is the heap size. This results in a total time complexity of `O(n log n)`.
Space
`O(1)` - The sort is performed in-place. The recursive `heapify` function uses `O(log n)` stack space in the worst case, but it can be implemented iteratively to achieve true `O(1)` space.
Trade-offs
Pros
Guaranteed
O(n log n)worst-case time complexity.Space complexity is
O(1), making it very memory-efficient.Perfectly satisfies all constraints of the problem.
Cons
Not a stable sort.
Can be slower in practice than a well-implemented Quick Sort due to poor cache locality.
Solutions
Solution
class Solution {private int[] nums;public int[] sortArray(int[] nums) { this.nums = nums; quikcSort(0, nums.length - 1); return nums; }private void quikcSort(int l, int r) { if (l >= r) { return; } int x = nums[(l + r) >> 1]; int i = l - 1, j = r + 1; while (i < j) { while (nums[++i] < x) { } while (nums[--j] > x) { } if (i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } quikcSort(l, j); quikcSort(j + 1, r); }}/** * @param {number[]} nums * @return {number[]} */ var sortArray = function ( nums,) { function quickSort(l, r) { if (l >= r) { return; } let i = l - 1; let j = r + 1; const x = nums[(l + r) >> 1]; while (i < j) { while (nums[++i] < x); while (nums[--j] > x); if (i < j) { [nums[i], nums[j]] = [nums[j], nums[i]]; } } quickSort(l, j); quickSort(j + 1, r); } const n = nums.length; quickSort(0, n - 1); return nums;};class Solution: def sortArray(self, nums: List[int]) -> List[int]: def quick_sort(l, r): if l >= r: return x = nums[randint(l, r)] i, j, k = l - 1, r + 1, l while k < j: if nums[k] < x: nums[i + 1], nums[k] = nums[k], nums[i + 1] i, k = i + 1, k + 1 elif nums[k] > x: j -= 1 nums[j], nums[k] = nums[k], nums[j] else: k = k + 1 quick_sort(l, i) quick_sort(j, r) quick_sort(0, len(nums) - 1) return numsclass Solution {public: vector<int> sortArray(vector<int> &nums) { function<void(int, int)> quick_sort = [&](int l, int r) { if (l >= r) { return; } int i = l - 1, j = r + 1; int x = nums[(l + r) >> 1]; while (i < j) { while (nums[++i] < x) { } while (nums[--j] > x) { } if (i < j) { swap(nums[i], nums[j]); } } quick_sort(l, j); quick_sort(j + 1, r); }; quick_sort(0, nums.size() - 1); return nums; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.