Think about your phone's contact list. Imagine if the names were stored in random order and you had to scroll through all 500 contacts every time you wanted to call someone.
Thankfully, contacts are arranged alphabetically, so you can jump straight to the right letter.
The same thing happens everywhere around you: exam results ranked by marks, products sorted by price on a shopping app, emails ordered by date, train schedules ordered by time.
Arranging data in a particular order is called sorting, and it is one of the most studied problems in computer science.
In the previous chapter, we saw that binary search can find an element among a billion values in about 30 steps, but only if the data is sorted. This chapter is an overview of sorting: what it means, the terms you need to know, and how the main sorting algorithms compare. The next chapters cover each algorithm in detail.
What is Sorting?
Sorting is the process of arranging the elements of a collection in a specific order, usually ascending (smallest to largest) or descending (largest to smallest), based on some comparison rule.
For example:
Unsorted: [42, 7, 19, 3, 25]
Ascending: [3, 7, 19, 25, 42]
Descending: [42, 25, 19, 7, 3]Sorting is not only for numbers. We can sort:
Strings alphabetically:
["Aarav", "Diya", "Rohan"]Dates from oldest to newest
Objects by a field, such as students by marks or products by price
All we need is a rule that tells us which of two elements should come first.
Why is Sorting Important?
Sorting is rarely the final goal. It is usually a step that makes other problems easier.
1. Faster Searching
Sorted data allows binary search: O(log n) instead of O(n).
2. Finding Duplicates
After sorting, equal elements sit next to each other:
[4, 1, 7, 4, 9, 1] → sort → [1, 1, 4, 4, 7, 9]
↑ ↑ ↑ ↑
duplicates are neighboursNow one simple pass that compares each element with the next one finds every duplicate.
3. Minimum, Maximum and Median
In a sorted array, the minimum is at index 0, the maximum at the last index, and the median in the middle.
4. A Building Block for Other Algorithms
Many techniques coming later in this course, such as two pointers and many greedy algorithms, start by sorting the input.
5. Better Presentation
Rank lists, leaderboards, price lists and search results all need sorted output.
Important Sorting Terminology
Before comparing sorting algorithms, we need a few terms. Interviewers use these words all the time.
In-Place Sorting
An algorithm is in-place if it sorts the data using only a small, constant amount of extra memory (O(1)), by rearranging elements inside the original array.
In-place → Bubble Sort, Selection Sort, Insertion Sort
Not in-place → Merge Sort (needs an extra array of size n)Quick Sort is usually also called in-place, even though its recursion uses O(log n) stack space on average.
Stable Sorting
This is the term students confuse most often.
A sorting algorithm is stable if elements with equal keys keep the same relative order they had before sorting.
Suppose we sort these students by marks:
Before: Aarav(85), Diya(92), Kabir(85), Meera(78)Aarav and Kabir both have 85, and Aarav comes first in the original list.
Stable sort: Meera(78), Aarav(85), Kabir(85), Diya(92) ← Aarav still before Kabir
Unstable sort: Meera(78), Kabir(85), Aarav(85), Diya(92) ← order may changeBoth results are correctly sorted by marks. The difference only matters when equal elements carry other information.
Why does this matter? Imagine the list was already sorted by name, and now you sort it by marks. A stable sort keeps students with the same marks in alphabetical order, so you effectively get "sorted by marks, then by name" for free.
For plain numbers, stability does not matter, because two equal 7s are indistinguishable.
Comparison-Based vs Non-Comparison Sorting
Comparison-based sorts decide the order only by comparing two elements at a time (
a < b?). Bubble, Selection, Insertion, Merge, Quick and Heap Sort are all comparison-based.Non-comparison sorts use properties of the values themselves, such as their digits or their range. Counting Sort and Radix Sort are examples.
Adaptive Sorting
An algorithm is adaptive if it runs faster when the input is already sorted or nearly sorted. Insertion Sort is the classic example: on an already sorted array it takes only O(n) time.
Internal vs External Sorting
Internal sorting → all the data fits in main memory (RAM). This is what most DSA problems assume.
External sorting → the data is too large for RAM and lives on disk. It is processed in chunks, usually with a merge-based approach.
The Main Sorting Algorithms
Here is a quick introduction to the algorithms we will study in the upcoming chapters.
Bubble Sort
Repeatedly compares neighbouring elements and swaps them if they are in the wrong order. Large elements "bubble up" to the end.
Selection Sort
Repeatedly selects the smallest remaining element and puts it in its correct position.
Insertion Sort
Builds the sorted part one element at a time, inserting each new element into its correct place, just like arranging playing cards in your hand.
Merge Sort
Splits the array into halves, sorts each half recursively, then merges the two sorted halves.
Quick Sort
Picks a pivot, places smaller elements on its left and larger ones on its right, then sorts both sides recursively.
Counting Sort and Radix Sort
Non-comparison sorts that work on integers in a limited range (Counting Sort) or digit by digit (Radix Sort).
Heap Sort is another important O(n log n) algorithm. It uses the heap data structure, so it fits naturally with the Heap chapter later in the course.
Comparing Sorting Algorithms
This table is worth remembering for interviews. Here n is the number of elements, k is the range of values (or the base for Radix Sort), and d is the number of digits.
Algorithm | Best | Average | Worst | Extra Space | Stable? |
|---|---|---|---|---|---|
Bubble Sort | O(n)* | O(n²) | O(n²) | O(1) | Yes |
Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
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) stack (average) | 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(n + k) | Yes** |
Radix Sort | O(d·(n + k)) | O(d·(n + k)) | O(d·(n + k)) | O(n + k) | Yes |
* Only with the "stop if no swaps happened" optimization, which we will add in the Bubble Sort chapter.
** The standard version that builds a separate output array is stable.
A simple way to group them:
Simple, O(n²) → Bubble, Selection, Insertion
Efficient, O(n log n) → Merge, Quick, Heap
Special cases, linear → Counting, RadixHow Fast Is O(n²) vs O(n log n)?
The difference between the two groups becomes huge as n grows:
n | n² | n log₂ n (approx.) |
|---|---|---|
10 | 100 | 33 |
1,000 | 1,000,000 | 10,000 |
1,000,000 | 1,000,000,000,000 | 20,000,000 |
For one million elements, an O(n²) sort needs around a trillion steps, while an O(n log n) sort needs around 20 million. That can be the difference between many minutes (or even hours) and a fraction of a second.
So why learn the O(n²) algorithms at all?
They are simple and teach the core ideas of comparing, swapping and shifting.
They are excellent for very small arrays. Real libraries often switch to Insertion Sort for small pieces of the array.
Interviewers frequently ask you to write or trace them.
The O(n log n) Limit
Here is an important theoretical fact:
No comparison-based sorting algorithm can do better than O(n log n) comparisons in the worst case.
The intuition: there are n! possible orderings of n elements, and each comparison gives only a yes/no answer, so it can at best cut the remaining possibilities in half. Telling apart n! possibilities therefore needs at least log₂(n!) comparisons, and log₂(n!) grows like n log n.
That is why Merge Sort and Heap Sort are considered optimal comparison sorts. Counting Sort and Radix Sort can beat this limit only because they do not compare elements; instead they rely on extra knowledge about the values, such as a small range of integers.
Sorting in Java
In real projects, you will almost always use Java's built-in sorting methods instead of writing your own.
Method | Algorithm used | Stable? |
|---|---|---|
| Dual-Pivot Quicksort | Not guaranteed (doesn't matter for primitives) |
| TimSort (a merge sort + insertion sort hybrid) | Yes |
| TimSort | Yes |
All of these run in O(n log n) time.
Let's see them in action:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class Student {
String name;
int marks;
Student(String name, int marks) {
this.name = name;
this.marks = marks;
}
@Override
public String toString() {
return name + "(" + marks + ")";
}
}
class Main {
public static void main(String[] args) {
// 1. Sorting primitives (ascending)
int[] numbers = {42, 7, 19, 3, 25, 7};
Arrays.sort(numbers);
System.out.println("Sorted ints: " + Arrays.toString(numbers));
// 2. Sorting Strings (alphabetical / lexicographic)
String[] names = {"Rohan", "Aarav", "meera", "Diya"};
Arrays.sort(names);
System.out.println("Sorted names: " + Arrays.toString(names));
// 3. Descending order needs a wrapper type like Integer
Integer[] boxed = {42, 7, 19, 3, 25, 7};
Arrays.sort(boxed, Collections.reverseOrder());
System.out.println("Descending: " + Arrays.toString(boxed));
// 4. Sorting a List
List<Integer> list = new ArrayList<>(List.of(5, 1, 4, 2, 3));
Collections.sort(list);
System.out.println("Sorted list: " + list);
// 5. Sorting objects by a key (stable sort)
List<Student> students = new ArrayList<>(List.of(
new Student("Aarav", 85),
new Student("Diya", 92),
new Student("Kabir", 85),
new Student("Meera", 78),
new Student("Rohan", 92)
));
students.sort(Comparator.comparingInt(s -> s.marks));
System.out.println("By marks (asc): " + students);
students.sort(Comparator.comparingInt((Student s) -> s.marks).reversed());
System.out.println("By marks (desc): " + students);
}
}Output:
Sorted ints: [3, 7, 7, 19, 25, 42]
Sorted names: [Aarav, Diya, Rohan, meera]
Descending: [42, 25, 19, 7, 7, 3]
Sorted list: [1, 2, 3, 4, 5]
By marks (asc): [Meera(78), Aarav(85), Kabir(85), Diya(92), Rohan(92)]
By marks (desc): [Diya(92), Rohan(92), Aarav(85), Kabir(85), Meera(78)]A few things to notice:
"meera"comes after"Rohan". String sorting compares character codes, and every uppercase letter comes before every lowercase letter. UseString.CASE_INSENSITIVE_ORDERas the comparator if you want to ignore case.Collections.reverseOrder()does not work withint[]. A comparator needs objects, so we usedInteger[].In the ascending result,
Aaravstays beforeKabir(both 85) because their original order was Aarav, then Kabir. That is stability in action.
How to Choose a Sorting Algorithm
Situation | Good choice |
|---|---|
Everyday code in Java |
|
Very small array, or nearly sorted data | Insertion Sort |
Need guaranteed O(n log n) and stability | Merge Sort |
Fast in practice, memory is limited | Quick Sort |
Guaranteed O(n log n) with O(1) extra space | Heap Sort |
Integers in a small known range | Counting Sort |
Writing to memory is very expensive | Selection Sort (at most n − 1 swaps) |
Learning, or teaching the basics | Bubble Sort |
Interview Tips
Know the comparison table above, especially which algorithms are stable and which are in-place.
Be able to explain stability with an example like the students list.
Remember that
Arrays.sorton primitives and objects uses different algorithms.When a problem seems hard, ask yourself: "Would sorting the input first make this easier?" Very often, sorting in
O(n log n)turns anO(n²)brute force into something much simpler.Unless an interviewer asks you to implement a sort, it is fine to use the built-in sort and say its complexity is
O(n log n).
The Main Idea
Sorting arranges data in a specific order, and it makes many other operations, such as searching, finding duplicates and finding medians, much easier.
The key terms:
In-place → uses O(1) extra memory
Stable → equal elements keep their original order
Comparison-based → decides order using a < b comparisons
Adaptive → faster on nearly sorted inputThe main groups:
O(n²) → Bubble, Selection, Insertion
O(n log n) → Merge, Quick (average), Heap
Linear-ish → Counting, Radix (for special inputs)No comparison sort can beat O(n log n) in the worst case. The simple O(n²) sorts are still worth learning because they build intuition — and we start with the simplest of them all, Bubble Sort.