Sort an Array
Medium · Heap / Priority Queue · Explanation and code example
Merge Sort
How it works
Merge sort divides the array into two halves, recursively sorts each half, and then merges the sorted halves. The merge step combines two sorted arrays into one by repeatedly picking the smaller element from the front of each array. This divide-and-conquer approach guarantees O(n log n) time regardless of input order.
Steps
- Base case: if the subarray has one or zero elements, it is already sorted.
- Find the middle index and recursively sort the left half (
ltomid) and right half (mid + 1tor). - Merge the two sorted halves:
- Create temporary arrays for
leftandrightportions. - Compare elements from both arrays and place the smaller one into the result.
- Copy any remaining elements from either array.
- Create temporary arrays for
- Return the sorted array.
Complexity
- Time complexity:
O(n log n) - Space complexity:
O(n)
Things to watch for
Using Naive Quick Sort Pivot Selection
Choosing the first or last element as the pivot without any randomization or median selection causes O(n^2) time complexity on sorted or nearly-sorted arrays. Always use randomized pivot selection or median-of-three to avoid worst-case performance on common input patterns.
Forgetting to Handle Negative Numbers in Radix Sort
Radix sort only works directly on non-negative integers. If you apply radix sort to an array containing negative numbers without first separating them, the algorithm produces incorrect results. You must handle negatives separately by converting them to positive, sorting, reversing, and negating back.
Stack Overflow in Recursive Implementations
Deep recursion in merge sort or quick sort can cause stack overflow on very large arrays. For production code, consider iterative implementations or ensure tail-call optimization where available. Some languages have strict stack limits that recursive sorting algorithms can exceed.
Python code example
from typing import List
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge(arr, L, M, R):
left, right = arr[L:M+1], arr[M+1:R+1]
i, j, k = L, 0, 0
while j < len(left) and k < len(right):
if left[j] <= right[k]:
arr[i] = left[j]
j += 1
else:
arr[i] = right[k]
k += 1
i += 1
while j < len(left):
arr[i] = left[j]
j += 1
i += 1
while k < len(right):
arr[i] = right[k]
k += 1
i += 1
def mergeSort(arr, l, r):
if l >= r:
return
m = (l + r) // 2
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
merge(arr, l, m, r)
mergeSort(nums, 0, len(nums) - 1)
return nums
C++ code example
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
private:
void mergeSort(vector<int>& arr, int l, int r) {
if (l >= r) return;
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
void merge(vector<int>& arr, int l, int m, int r) {
vector<int> temp;
int i = l, j = m + 1;
while (i <= m && j <= r) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i++]);
} else {
temp.push_back(arr[j++]);
}
}
while (i <= m) temp.push_back(arr[i++]);
while (j <= r) temp.push_back(arr[j++]);
for (int i = l; i <= r; i++) {
arr[i] = temp[i - l];
}
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.