DSA in Java: Sorting Algorithms Explained (Beginner Guide)

Sorting — arranging items in order — is one of the most studied problems in computer science, and for good reason: sorted data unlocks fast techniques like the binary search you just learned. In this lesson you'll understand how sorting actually works under the hood, meet the algorithms interviewers ask about, and — just as importantly — learn what to use in real Java code.

Start simple: Bubble Sort (to build intuition)

Bubble sort is the "hello world" of sorting. It repeatedly walks the array, swapping any two neighbours that are out of order. Big values "bubble" to the end. Nobody uses it in production, but it makes the idea of sorting concrete:

void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {        // out of order? swap them
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Two nested loops → O(n²). That's slow for big inputs, which is exactly why cleverer algorithms exist. Selection sort and insertion sort are two other simple O(n²) sorts in the same family — worth knowing by name, and insertion sort is genuinely fast on small or nearly-sorted data.

The fast sorts: Merge Sort & Quick Sort

The efficient sorts run in O(n log n) — that "log" appears because, like binary search, they repeatedly split the problem in half. Both use the recursion you learned in Lesson 4.

Merge Sort — divide and conquer

The idea: split the array in half, sort each half (recursively), then merge the two sorted halves back together. Merging two already-sorted lists is easy and fast.

Merge sort is reliably O(n log n) in every case, and it's stable (keeps equal elements in their original order). Its one cost: it needs O(n) extra memory for the merging.

Quick Sort — pick a pivot and partition

Quick sort picks a "pivot" element and partitions the array so smaller values go left of the pivot and larger go right — then recursively sorts each side. On average it's O(n log n) and very fast in practice with low memory overhead. Its worst case is O(n²) (rare, with bad pivot choices), but good implementations avoid that.

Comparing the sorts

In real Java code: just use the built-in sort

Here's the honest truth for everyday programming: you almost never write your own sort. Java's built-in sort is highly optimised (a tuned merge/insertion hybrid called TimSort for objects, dual-pivot quicksort for primitives), and it runs in O(n log n):

int[] nums = {8, 3, 5, 1};
Arrays.sort(nums);                    // [1, 3, 5, 8]

List<String> names = ...;
Collections.sort(names);              // natural (alphabetical) order

// custom order with a comparator (e.g. by length):
names.sort(Comparator.comparingInt(String::length));

So why learn the algorithms at all? Because interviewers ask you to explain and sometimes implement them, and because understanding how sorting achieves O(n log n) deepens your grasp of recursion, divide-and-conquer, and complexity.

When I was preparing for interviews, I made the mistake of memorising sorting code without understanding it — and promptly blanked under pressure. What actually stuck was the ideas: bubble sort swaps neighbours (slow, O(n²)); merge sort splits and merges; quick sort partitions around a pivot; both fast ones are O(n log n) via divide-and-conquer. Learn the concepts and you can reconstruct the code. And in real projects? Reach for Arrays.sort / Collections.sort every single time — reinventing a sort in production is almost always the wrong call.

Key takeaways

• Simple sorts (bubble, selection, insertion) are O(n²) — good for learning, slow at scale.
• Merge sort (split & merge) and quick sort (pivot & partition) are O(n log n) via divide-and-conquer.
• Merge sort is stable but uses extra memory; quick sort is fast and in-place on average.
• In real code, use Arrays.sort / Collections.sort — learn the algorithms for interviews and understanding.

← Previous: DSA Lesson 5 — Searching
Next: DSA Lesson 7 — Linked Lists →
↑ Back to the DSA roadmap