Chapter 14 of 65

Sorting Algorithms

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 neighbours

Now 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 change

Both 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, Radix

How 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?

Arrays.sort(int[]) and other primitive arrays

Dual-Pivot Quicksort

Not guaranteed (doesn't matter for primitives)

Arrays.sort(Object[])

TimSort (a merge sort + insertion sort hybrid)

Yes

Collections.sort(list) / list.sort(...)

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. Use String.CASE_INSENSITIVE_ORDER as the comparator if you want to ignore case.

  • Collections.reverseOrder() does not work with int[]. A comparator needs objects, so we used Integer[].

  • In the ascending result, Aarav stays before Kabir (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

Arrays.sort / Collections.sort

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.sort on 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 an O(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 input

The 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.