Which Sorting Algorithms to Learn for Interviews
Bubble sort is rarely the answer in a coding interview. See which sorting algorithms to learn, their time complexity, and the problems where each one shows up.
On this page
You may have to write bubble sort in a college viva or a basic written test, but in a coding interview it is almost never the answer. It runs in O(n^2), so an interviewer who asks you to sort a large input expects you to call the built-in sort or to use a smarter algorithm. Spend an hour on bubble sort, not a week.
What interviews reward is knowing which sorting idea sits inside a problem.
The sorts worth knowing, in one table
| Algorithm | Time (typical) | Extra space | Stable | Where it shows up |
|---|---|---|---|---|
| Bubble sort | O(n^2) | O(1) | Yes | Viva questions, explaining swaps |
| Insertion sort | O(n^2), O(n) if nearly sorted | O(1) | Yes | Small inputs, nearly sorted data |
| Merge sort | O(n log n) | O(n) | Yes | Counting inversions, sorting linked lists |
| Quick sort | O(n log n) average, O(n^2) worst | O(log n) | No | Partition problems, quickselect |
| Heap sort | O(n log n) | O(1) | No | Top-k, priority queues |
| Counting sort | O(n + k) | O(k) | Yes | Small value ranges |
Stable means equal elements keep their original order, which matters when you sort records by one field and then by another.
Bubble sort in ten minutes
Compare neighbours and swap them if they are out of order. After the first pass the largest element sits at the end, after the second pass the second largest does, and so on. Add a flag that records whether a pass swapped anything. If a pass swaps nothing, stop: the array is sorted, and the best case drops to O(n).
That is the entire idea. Try it on [5, 1, 4, 2] by hand and count the swaps. You can practise it on the Bubble Sort problem.
The three ideas that appear in real problems
Sort first, then scan. Merge Intervals sorts by start time and then merges in one pass. Many two-pointer problems begin with a sort. Cost: O(n log n) for the sort, which usually dominates.
Partition. Quick sort's partition step puts smaller elements on one side of a pivot. The same move solves Sort Colors with three groups, and quickselect finds the k-th largest element in O(n) on average.
Merge two sorted halves. This is the heart of merge sort. It also counts inversions in O(n log n) instead of O(n^2), which the Count Inversions problem puts to work.
What to say if you are asked to sort in an interview
Say you would use the built-in sort, name its cost, and ask whether the input is nearly sorted or has a small range of values. That question alone shows you know that counting sort or insertion sort can beat the general case. Then move on to the real problem.
Next step: open the Sorting topic, solve merge sort and count inversions in that order, and note in one line which sorting idea each problem uses.
Frequently asked questions
Why is bubble sort rarely the expected answer in coding interviews?
It runs in O(n^2) time, so interviewers expect you to use built-in sorts or smarter algorithms for large inputs.
What does it mean for a sorting algorithm to be stable?
Stable means equal elements keep their original order, which matters when sorting records by multiple fields sequentially.
Which sorting algorithm is best for counting inversions?
Merge sort is used to count inversions in O(n log n) time, which is faster than the O(n^2) approach.
What should you say if asked to sort data in an interview?
Mention using the built-in sort, state its cost, and ask if the input is nearly sorted or has a small value range.
Practice what you just read
Open one in the editor and submit it. Your code is checked against hidden tests in C++, Java, Python and JavaScript. No account needed.
Keep reading
Your First 30 DSA Problems: What Order to Solve Them In
Stop solving random problems. Master these 30 DSA questions in a specific order to build the logic patterns required for your coding interviews.
Common Edge Cases in DSA Problems and How to Catch Them
Master coding interviews on DSA Tracker by learning how to catch hidden edge cases like empty inputs, duplicates, and integer overflow before they break your.