Interview Concept: Stable vs Unstable Sorting Algorithms
Stable vs unstable sorting explained: what stability means, which algorithms are stable, and why it matters when sorting by multiple keys. With a comparison table.
-
Arrays
- Find the Largest Element in an Array
- Find the Second Largest Element in an Array
- Reverse an Array In Place
- Check if an Array Is Sorted
- Remove Duplicates from a Sorted Array
- Move Zeroes to the End of an Array
- Rotate an Array by K Positions
- Two Sum
- Maximum Subarray Sum (Kadane's Algorithm)
- Best Time to Buy and Sell Stock
- Sort an Array of 0s, 1s and 2s (Dutch National Flag)
- Find the Missing Number in an Array
- Find the Duplicate Number in an Array
- Union of Two Sorted Arrays
- Intersection of Two Sorted Arrays
- Prefix Sum Array and Range Sum Queries
- Majority Element (Boyer-Moore Voting Algorithm)
- Merge Overlapping Intervals
- Next Permutation
- Product of Array Except Self
- Subarray Sum Equals K
- Merge Two Sorted Arrays In Place
- Maximum Product Subarray
- 3Sum: Find All Triplets That Sum to Zero
- Trapping Rain Water
- Container With Most Water
- Rotate Image (Matrix 90 Degree Rotation)
- Spiral Matrix Traversal
- Set Matrix Zeroes
- Kth Largest Element in an Array (Quickselect)
-
Strings
- Reverse a String In Place
- Check if a String Is a Palindrome
- Check if Two Strings Are Anagrams
- Count Frequency of Characters in a String
- First Non-Repeating Character in a String
- Reverse Words in a Sentence
- Check if a String Contains Only Digits
- Remove Duplicate Characters from a String
- Longest Substring Without Repeating Characters
- Group Anagrams
- Valid Parentheses
- String to Integer (atoi)
- Longest Common Prefix
- Implement strStr() - Naive Pattern Matching
- Run-Length Encoding of a String
- Check if a String Is a Rotation of Another
- Longest Palindromic Substring
- Minimum Window Substring
- Zigzag Conversion
- KMP Pattern Matching Algorithm
- Rabin-Karp Pattern Matching Algorithm
- Z-Algorithm for Pattern Matching
- Longest Palindromic Subsequence
- Edit Distance Between Two Strings
- Word Break Problem
- Decode Ways
- String Compression (In-Place)
- Count and Say
- Roman to Integer
- Integer to Roman
- Valid Palindrome II (At Most One Deletion)
- Longest Repeating Character Replacement
- Multiply Two Numbers Represented as Strings
- Why Strings Are Immutable (Interview Concept)
- Time Complexity of Common String Operations (Interview Co...
-
Sliding Window
- Maximum Sum Subarray of Size K (Fixed Window)
- Average of All Subarrays of Size K
- Maximum Number of Vowels in a Substring of Length K
- First Negative Integer in Every Window of Size K
- K Radius Subarray Averages
- Max Consecutive Ones
- Max Consecutive Ones III (At Most K Flips)
- Longest Subarray With Sum At Most K
- Minimum Size Subarray Sum
- Fruit Into Baskets (Longest Subarray With At Most 2 Disti...
- Longest Subarray With At Most K Distinct Elements
- Subarray Product Less Than K
- Maximum Average Subarray I
- Sliding Window Maximum (Monotonic Deque)
- Find All Anagrams in a String (Sliding Window)
- Repeated DNA Sequences (Fixed Window Hashing)
- Longest Turbulent Subarray
- Maximum Erasure Value (Longest Unique Subarray Sum)
- Longest Continuous Increasing Subsequence
- Grumpy Bookstore Owner
- Maximum Points You Can Obtain from Cards
- Binary Subarrays With Sum (Exactly K Trick)
- Count Number of Nice Subarrays (Exactly K Odd Numbers)
- Continuous Subarray Sum (Multiple of K)
- Minimum Operations to Reduce X to Zero
- Maximum Frequency After K Increments
- Sliding Window Median
- Substring With Concatenation of All Words
- Count Complete Subarrays in an Array
- Number of Subarrays With Bounded Maximum
- Maximum Sum of Distinct Subarrays With Length K
- Shortest Subarray With Sum At Least K (With Negatives)
- Fixed-Size vs Variable-Size Sliding Window (Interview Con...
- When to Use Sliding Window vs Two Pointers (Interview Con...
- Recognizing a Sliding Window Problem (Interview Concept)
-
Two Pointers
- Two Sum II - Input Array Is Sorted
- Valid Palindrome (Two Pointer Check)
- Reverse Vowels of a String
- Remove Element In Place
- Move Zeroes Using Two Pointers
- 3Sum Closest
- 4Sum
- Sort Array By Parity
- Squares of a Sorted Array
- Merge Two Sorted Arrays (Two Pointer)
- Intersection of Two Arrays II
- Backspace String Compare
- Trapping Rain Water (Two Pointer Approach)
- Container With Most Water (Two Pointer Approach)
- Partition Labels
- Sort Colors (Dutch National Flag Two Pointer)
- Remove Duplicates from Sorted Array II
- Linked List Cycle Detection (Fast and Slow Pointers)
- Middle of the Linked List
- Palindrome Linked List Check
- Boats to Save People
- Valid Triangle Number
- Minimum Number of Swaps to Make Sequences Increasing
- Sentence Similarity Using Two Pointers
- Shortest Distance to a Character
- Interleaving String Check
- DNA Complement Matching
- Is Subsequence Check (Two Pointer)
- Interview Concept: Same Direction vs Opposite Direction Two Pointers
- Interview Concept: Fast and Slow Pointer Technique Explained
-
Searching & Binary Search
- Binary Search (Classic Iterative)
- Binary Search (Recursive)
- Search Insert Position
- First and Last Position of Element in Sorted Array
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II (With Duplicates)
- Find Minimum in Rotated Sorted Array
- Find Peak Element
- Sqrt(x) Using Binary Search
- Koko Eating Bananas
- Capacity To Ship Packages Within D Days
- Split Array Largest Sum
- Median of Two Sorted Arrays
- Search a 2D Matrix
- Search a 2D Matrix II
- Find K Closest Elements
- Kth Smallest Element in a Sorted Matrix
- Aggressive Cows (Binary Search on Answer)
- Allocate Minimum Number of Pages
- Single Element in a Sorted Array
- Find the Smallest Divisor Given a Threshold
- Binary Search on a Function (Ternary Search Alternative)
- Count of Smaller Numbers After Self
- Time Based Key-Value Store
- Guess Number Higher or Lower
- H-Index II
- Find Right Interval
- Random Pick with Weight
- Interview Concept: Lower Bound vs Upper Bound Binary Search
- Interview Concept: Binary Search on Answer Pattern Explained
-
Sorting
- Bubble Sort Implementation
- Selection Sort Implementation
- Insertion Sort Implementation
- Merge Sort Implementation
- Quick Sort Implementation
- Heap Sort Implementation
- Counting Sort Implementation
- Radix Sort Implementation
- Bucket Sort Implementation
- Sort an Array (Built-in vs Custom Comparator)
- Merge Intervals Using Sorting
- Largest Number Formed from an Array
- Custom Sort String
- Sort Characters By Frequency
- Kth Largest Element (Sorting Approach)
- Relative Sort Array
- Wiggle Sort
- Wiggle Sort II
- H-Index (Sorting Approach)
- Meeting Rooms (Can Attend All Meetings)
- Meeting Rooms II (Minimum Rooms Required)
- Sort a Nearly Sorted (K-Sorted) Array
- Pancake Sort
- Count Inversions in an Array
- Sort an Array of 0s 1s and 2s Using Counting Sort
- Maximum Gap (Bucket Sort Approach)
- Valid Anagram Using Sorting
- Sort a Linked List (Merge Sort Approach)
- Interview Concept: Stable vs Unstable Sorting Algorithms
- Interview Concept: Choosing the Right Sorting Algorithm for the Situation
What Is a Stable Sort?
A sort is stable if elements that compare equal keep their original relative order after sorting. If two records have the same key, a stable sort guarantees the one that appeared first in the input still appears first in the output.
Why Stability Matters
- Sorting by multiple keys: sort by a secondary key first, then a stable sort on the primary key preserves the secondary order.
- Example: sort people by age, then stably by city — within each city, people stay ordered by age.
- Databases and spreadsheets rely on stability for predictable multi-column sorting.
Which Algorithms Are Stable?
| Stable | Not stable (by default) |
|---|---|
| Bubble sort | Selection sort |
| Insertion sort | Quick sort |
| Merge sort | Heap sort |
| Counting sort | Shell sort |
| Radix sort (uses stable counting) |
Note: an unstable sort can be made stable by adding the original index as a tie-breaker in the comparison.
Language Defaults
- Python
sort/sorted(Timsort): stable. - Java
Arrays.sorton objects (Timsort): stable; on primitives (dual-pivot quicksort): not stable. - C++
std::sort: not guaranteed stable; usestd::stable_sortwhen you need stability.
Key Takeaways
- Stability preserves the input order of equal keys.
- Merge, insertion, counting, and radix sort are stable; quick, heap, and selection are not.
- Add the original index as a tie-breaker to make any sort behave stably.
- Reference: CLRS, Ch. 8; Wikipedia, "Sorting algorithm" (stability).