Sorting Algorithm Comparison
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| std::sort (C++) | O(n log n) | O(n log n) | O(n log n) | O(log n) | No |
C++ sort Usage
C++
#include <algorithm>
vector<int> v = {5,3,1,4,2};
sort(v.begin(), v.end()); // ascending → {1,2,3,4,5}
sort(v.begin(), v.end(), greater<int>()); // descending → {5,4,3,2,1}
// Custom comparator — sort pairs by second element descending
vector<pair<int,int>> pairs = {{1,5},{2,3},{3,7}};
sort(pairs.begin(), pairs.end(), [](auto& a, auto& b){
return a.second > b.second; // sort by second descending
});
// Sort strings by length
vector<string> words = {"banana","fig","apple"};
sort(words.begin(), words.end(), [](auto& a, auto& b){
return a.size() < b.size();
});
// stable_sort preserves relative order of equal elements
stable_sort(v.begin(), v.end());
Merge Sort (Know This Cold)
Divide and conquer. Split in half, sort each half, merge. Guaranteed O(n log n). Used in inversion count problems.
C++
void merge(vector<int>& arr, int l, int m, int r) {
vector<int> left(arr.begin()+l, arr.begin()+m+1);
vector<int> right(arr.begin()+m+1, arr.begin()+r+1);
int i=0, j=0, k=l;
while (i<left.size() && j<right.size())
arr[k++] = (left[i]<=right[j]) ? left[i++] : right[j++];
while (i<left.size()) arr[k++]=left[i++];
while (j<right.size()) arr[k++]=right[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {
if (l >= r) return;
int m = l + (r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
// Time: O(n log n) Space: O(n) Stable: Yes
Interactive: Merge Sort Steps
Watch merge sort divide the array in half, recursively sort each half, then merge them back in order.
Practice Problems
#912Sort an ArrayMedium
Sort an array using a sorting algorithm (must be better than O(n²)).
Pattern: Implement merge sort from scratch. Good practice for the divide-and-conquer mindset.
C++
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, nums.size()-1);
return nums;
}
// Use the mergeSort implementation above
// Time: O(n log n) Space: O(n)
#56Merge IntervalsMedium
Given array of intervals, merge all overlapping intervals and return non-overlapping intervals.
Pattern: Sort by start. Iterate: if current start ≤ last end, merge by extending end to max. Otherwise, add new interval.
C++
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res = {intervals[0]};
for (int i=1; i<intervals.size(); i++) {
if (intervals[i][0] <= res.back()[1])
res.back()[1] = max(res.back()[1], intervals[i][1]);
else
res.push_back(intervals[i]);
}
return res;
}
// Time: O(n log n) Space: O(n)
#75Sort Colors (Dutch Flag)Medium
Sort array containing only 0, 1, 2 in-place in one pass without extra space.
Pattern: Dutch National Flag — three pointers: lo (0s boundary), mid (current), hi (2s boundary). Swap to correct region.
C++
void sortColors(vector<int>& nums) {
int lo=0, mid=0, hi=nums.size()-1;
while (mid <= hi) {
if (nums[mid]==0) swap(nums[lo++], nums[mid++]);
else if (nums[mid]==2) swap(nums[mid], nums[hi--]);
else mid++;
}
}
// Time: O(n) Space: O(1) One pass!
#179Largest NumberMedium
Given non-negative integers, arrange them to form the largest number. E.g., [3,30,34,5,9] → "9534330".
Pattern: Custom sort. Compare a+b vs b+a as strings. If "ab" > "ba", put a before b.
C++
string largestNumber(vector<int>& nums) {
vector<string> strs;
for (int n : nums) strs.push_back(to_string(n));
sort(strs.begin(), strs.end(), [](auto& a, auto& b){
return a+b > b+a; // key comparison
});
if (strs[0]=="0") return "0";
string res;
for (auto& s : strs) res += s;
return res;
}
// Time: O(n log n * k) where k = avg digit length
#148Sort ListMedium
Sort a linked list in O(n log n) time using O(1) space (bottom-up merge sort).
Pattern: Merge sort on linked list. Find midpoint, split, recurse, merge. Bottom-up approach achieves O(1) extra space.
C++
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummy(0); ListNode* cur=&dummy;
while(l1&&l2){ if(l1->val<=l2->val){cur->next=l1;l1=l1->next;}
else{cur->next=l2;l2=l2->next;} cur=cur->next;}
cur->next = l1?l1:l2;
return dummy.next;
}
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow=head, *fast=head->next;
while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}
ListNode* mid=slow->next; slow->next=nullptr;
return merge(sortList(head), sortList(mid));
}
// Time: O(n log n) Space: O(log n) call stack
#315Count of Smaller Numbers After SelfHard
For each element, count how many elements to its right are smaller. Classic merge sort + count problem.
Pattern: Modified merge sort. Count inversions during merge step. When right element merges before left element, count += remaining left elements.
C++
vector<int> counts;
void mergeCount(vector<pair<int,int>>& arr, int l, int r) {
if(r-l<=1) return;
int m=(l+r)/2;
mergeCount(arr,l,m); mergeCount(arr,m,r);
vector<pair<int,int>> tmp;
int j=m;
for(int i=l,rightCount=0; i<m; i++) {
while(j<r && arr[j].first<arr[i].first) { j++; rightCount++; }
counts[arr[i].second] += rightCount;
}
inplace_merge(arr.begin()+l, arr.begin()+m, arr.begin()+r);
}
vector<int> countSmaller(vector<int>& nums) {
int n=nums.size();
counts.assign(n,0);
vector<pair<int,int>> arr;
for(int i=0;i<n;i++) arr.push_back({nums[i],i});
mergeCount(arr,0,n);
return counts;
}
// Time: O(n log n) Space: O(n)
#215Kth Largest Element in an ArrayMedium
Find the kth largest element in an unsorted array (not the kth distinct).
Pattern: Quickselect — partition like quicksort. If pivot lands at position k, done. Otherwise recurse only into the half containing k. Average O(n), worst O(n²).
C++
int partition(vector<int>& a, int lo, int hi) {
int pivot=a[hi], i=lo;
for(int j=lo;j<hi;j++) if(a[j]>=pivot) swap(a[i++],a[j]);
swap(a[i],a[hi]);
return i;
}
int findKthLargest(vector<int>& nums, int k) {
int lo=0, hi=nums.size()-1;
k--; // 0-indexed target position
while(lo<=hi) {
int p=partition(nums,lo,hi);
if(p==k) return nums[p];
else if(p<k) lo=p+1;
else hi=p-1;
}
return -1;
}
// Time: O(n) avg, O(n²) worst Space: O(1)
Rule of thumb: In interviews, just use std::sort unless the problem specifically asks for a sort algorithm. Know merge sort for inversion counting and sort list problems. Know counting sort when values are small and bounded.
Deeper Understanding
Why Sorting Isn't Just std::sort
Stability: When Order of Equals Matters
When to Use Which Algorithm
General case — need fastest sort
Use std::sort (introsort). O(n log n) guaranteed, O(log n) space. Unstable — fine for primitives.
Need stable sort (preserve relative order of equals)
Use std::stable_sort (merge sort). O(n log n), O(n) space. Required when secondary sort key matters.
Values are small integers in range [0, k]
Use counting sort. O(n + k) time and space. Sort array of 0/1/2 in one pass (Dutch Flag).
Sort a linked list in O(1) extra space
Use bottom-up merge sort. No random access needed. O(n log n), O(1) space iterative.
Find kth largest/smallest element
Use quickselect. O(n) average — no need to fully sort. Partition and recurse into one side only.
Common Misconceptions
"Quicksort is always O(n log n)"
Wrong. Worst case O(n²) on already-sorted input with bad pivot. std::sort avoids this with random pivot + heapsort fallback.
"Merge sort is strictly better because it's always O(n log n)"
Wrong. Merge sort needs O(n) extra space. Quicksort is in-place with better cache locality in practice.
"Always sort first when you see an array problem"
Caution. Sorting destroys original index information. If indices matter, either track them or use a different approach.
Follow-Up Problems to Push Deeper
Count inversions in an array
Merge sort augmentation — count right-before-left merges. Same O(n log n) skeleton as standard merge sort.
#493 Reverse Pairs (Hard)
Modified inversion count: pairs (i,j) where i < j and nums[i] > 2×nums[j]. Solve in merge step.
Top-K with a heap vs quickselect
Min-heap of size k gives O(n log k) — good when k is small. Quickselect gives O(n) avg — better when k ≈ n/2.