Sorting Algorithms in Java

Sorting is the first real algorithm topic every student meets, and it shows up everywhere: DSA papers, university practicals, coding rounds and interview questions. This tutorial covers three of the most asked sorting algorithms – Merge Sort, Heap Sort and Radix Sort – with working Java code, dry runs, complexity tables and the exact points examiners look for.

What You Will Learn

How each algorithm works, step by step
Complete, runnable Java code for all three
Time and space complexity, with the reason behind each
Which algorithm to pick for which type of data
Common mistakes and viva questions

Quick Recap: What Is a Sorting Algorithm

A sorting algorithm arranges data in a defined order (ascending or descending)
Comparison based: decides order by comparing elements – Merge Sort, Heap Sort, Quick Sort
Non-comparison based: uses digits, keys or counts instead – Radix Sort, Counting Sort
Stable sort: equal elements keep their original relative order
In-place sort: uses only a constant amount of extra memory

Comparison at a Glance

Algorithm	Best	Average	Worst	Space	Stable	In-place
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Yes
Radix Sort	O(n * k)	O(n * k)	O(n * k)	O(n + b)	Yes	No

Here n = number of elements, k = number of digits in the largest number, b = base (10 for decimal digits).

1. Merge Sort

Merge Sort follows the divide and conquer approach. It keeps splitting the array until every part has a single element, then merges those parts back in sorted order.

How It Works

Divide: split the array into two halves at the middle index
Conquer: sort both halves recursively using the same method
Merge: combine the two sorted halves into one sorted array by repeatedly taking whichever half currently has the smaller value at its front
When one half runs out, copy the remaining elements of the other half as they are

Dry Run

Input: 12, 11, 13, 5, 6, 7
Split: [12, 11, 13] and [5, 6, 7]
Split again: [12], [11, 13] and [5], [6, 7]
Merge back: [11, 12, 13] and [5, 6, 7]
Final merge: 5, 6, 7, 11, 12, 13

Java Code

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr.length < 2) {
            return; // already sorted
        }

        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {   // <= keeps the sort stable
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("Sorted array  : " + Arrays.toString(arr));
    }
}

Output

Original array: [12, 11, 13, 5, 6, 7]
Sorted array  : [5, 6, 7, 11, 12, 13]

Points to Remember

Time complexity is O(n log n) in every case, so performance never degrades
Needs O(n) extra space for the temporary sub-arrays
Stable, which makes it useful when sorting records by more than one field
Preferred for linked lists and external sorting of large files

2. Heap Sort

Heap Sort uses the binary heap data structure. It first converts the array into a max heap, then repeatedly moves the largest element to the end of the array.

How It Works

Build a max heap from the array so the largest element sits at index 0
Swap the root with the last element of the unsorted part
Reduce the heap size by one, since the last position is now fixed
Heapify the root again to restore the max heap property
Repeat until only one element is left

Heap Index Rules

Left child of index i is at 2i + 1
Right child of index i is at 2i + 2
Parent of index i is at (i – 1) / 2
Heap building starts from index n/2 – 1, the last non-leaf node

Java Code

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // Step 1: build a max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Step 2: move the largest element to the end, one by one
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("Sorted array  : " + Arrays.toString(arr));
    }
}

Output

Original array: [12, 11, 13, 5, 6, 7]
Sorted array  : [5, 6, 7, 11, 12, 13]

Points to Remember

Extra memory stays constant at O(1), since all swaps happen inside the same array
Quick Sort can drop to O(n squared) on bad input, but Heap Sort never crosses O(n log n)
Equal values can get separated during the root swap, so the sort is not stable
The heap is built in O(n), and each of the n extractions costs O(log n)
The same heap idea powers PriorityQueue in Java, task schedulers and Dijkstra’s algorithm

3. Radix Sort

Radix Sort does not compare elements at all. It sorts numbers digit by digit, starting from the least significant digit, using a stable Counting Sort at every pass.

How It Works

Find the maximum value to know how many digits are needed
Sort the array by the units digit using Counting Sort
Repeat for the tens digit, then hundreds, and so on
After the last digit pass, the array is fully sorted
Counting Sort must be stable, otherwise the earlier digit order is lost

Dry Run

Input: 170, 45, 75, 90, 802, 24, 2, 66
After units digit: 170, 90, 802, 2, 24, 45, 75, 66
After tens digit: 802, 2, 24, 45, 66, 170, 75, 90
After hundreds digit: 2, 24, 45, 66, 75, 90, 170, 802

Java Code

import java.util.Arrays;

public class RadixSort {

    public static void radixSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }

        int max = Arrays.stream(arr).max().getAsInt();

        // one Counting Sort pass per digit position
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // count how many numbers have each digit
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // convert counts into positions
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // build the output array from right to left to stay stable
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original array: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("Sorted array  : " + Arrays.toString(arr));
    }
}

Output

Original array: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted array  : [2, 24, 45, 66, 75, 90, 170, 802]

Points to Remember

Runs in O(n * k), which beats O(n log n) when the numbers have few digits
Works only on integers or fixed length keys, not on arbitrary objects
This version does not handle negative numbers without extra changes
Stable, and always uses O(n + b) extra memory

Which Sorting Algorithm Should You Use

Situation	Best Choice	Reason
Sorting objects where order of equal items matters	Merge Sort	It is stable
Memory is limited	Heap Sort	Sorts in place with O(1) space
Large lists of integers with few digits	Radix Sort	Linear time per pass
Sorting a linked list	Merge Sort	No random access needed
Worst case must stay predictable	Heap Sort	Always O(n log n)

Common Mistakes to Avoid

Using a strict less than check while merging, which breaks stability in Merge Sort
Forgetting the base case in Merge Sort recursion, causing a stack overflow
Building the heap from index 0 instead of n/2 – 1, which wastes passes
Running the Heap Sort extraction loop down to i = 0 instead of i > 0
Filling the Counting Sort output array left to right, which destroys stability in Radix Sort
Passing negative numbers to this Radix Sort implementation

Interview and Viva Questions

Why is Merge Sort preferred over Quick Sort for linked lists
Why is Heap Sort not stable
Why is building a heap O(n) and not O(n log n)
When does Radix Sort become slower than Merge Sort
What does Java’s Arrays.sort use internally for primitives and for objects
Explain the difference between stable and in-place sorting with an example

Frequently Asked Questions

Which of these three is the fastest?
For integers with a small number of digits, Radix Sort usually wins. For general data, Merge Sort and Heap Sort both run in O(n log n), and Merge Sort is normally faster in practice because of better cache behaviour.

Is Heap Sort used in real projects?
The heap structure itself is used far more often than the sort, mainly in priority queues, task schedulers and graph algorithms such as Dijkstra.

Can Radix Sort handle strings?
Yes, if the strings have a fixed length or are padded. Each character position is treated like a digit.

How do I sort in descending order?
For Merge Sort, reverse the comparison during merging. For Heap Sort, build a min heap instead of a max heap. For Radix Sort, reverse the final array.

Conclusion

Merge Sort: predictable, stable, needs extra memory
Heap Sort: predictable, in place, not stable
Radix Sort: fastest for integer keys, limited to digit based data
Practice each one on paper first, then run the code and change the input array

Once you are comfortable with these three, move on to Quick Sort, Counting Sort and Bucket Sort to complete your sorting preparation.

Video explanations for Java topics are available on our channel: Java Video Playlists

Need a Complete Java Project?

Get full source code, database file, report, synopsis and PPT for BCA, MCA, B.Tech and Diploma final year submissions, with setup support and instant delivery.

Chat on WhatsApp for details

sorting algorithms visualized
sorting algorithms python
sorting algorithms in c
sorting algorithms in java
sorting algorithms time complexity
sorting algorithms w3schools
sorting algorithms pdf
sorting algorithms visualizer

2 responses to “Sorting Algorithms in Java”

Java tutorial Basics to Advance says:

August 26, 2026 at 11:53 am

[…] 🚀 Sorting Algorithms: Merge, Heap, and Radix With Code […]

Java Collection says:

August 26, 2026 at 12:10 pm

[…] 🚀 Sorting Algorithms: Merge, Heap, and Radix With Code […]

Sorting Algorithms in Java