Java Sorting Algorithms Guide: Merge Sort, Quick Sort, Heap Sort, TimSort, Radix Sort (2025)

Sorting algorithms are fundamental to computer science and software development. This comprehensive guide explores five essential sorting algorithms in Java, their implementations, performance characteristics, and use cases.

Introduction to Sorting Algorithms

Sorting algorithms can be categorized based on several characteristics:

• Stability: Whether equal elements maintain their relative order
• In-place: Whether the algorithm requires additional memory
• Time Complexity: Best, average, and worst-case performance
• Space Complexity: Additional memory requirements

Merge Sort

Characteristics

• Time Complexity: O(n log n) always
• Stable: Yes
• In-place: No
• Space Complexity: O(n)

Implementation

public class MergeSort {
    public static void sort(int[] arr) {
        if (arr.length < 2) return;
        
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];
        
        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);
        
        sort(left);
        sort(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]) {
                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++];
        }
    }
}

Use Cases

• Large datasets where stability is required
• External sorting (sorting data that doesn't fit in memory)
• When consistent O(n log n) performance is needed

Quick Sort

Characteristics

• Time Complexity: Best/Average: O(n log n), Worst: O(n²)
• Stable: No
• In-place: Yes
• Space Complexity: O(log n) for recursion stack

Implementation

public class QuickSort {
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    
    private static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Use Cases

• General-purpose sorting when stability is not required
• When average-case performance is more important than worst-case
• In-memory sorting of large datasets

Heap Sort

Characteristics

• Time Complexity: O(n log n)
• Stable: No
• In-place: Yes
• Space Complexity: O(1)

Implementation

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // Extract elements from heap
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            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) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Use Cases

• When memory usage is a concern
• When guaranteed O(n log n) performance is needed
• When stability is not required

TimSort

Characteristics

• Time Complexity: Best: O(n), Average/Worst: O(n log n)
• Stable: Yes
• In-place: Yes
• Space Complexity: O(n)

Implementation

// TimSort is complex to implement from scratch
// Here's how to use Java's built-in TimSort
import java.util.Arrays;

public class TimSortExample {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        
        // Using Arrays.sort() which implements TimSort
        Arrays.sort(arr);
        
        // For objects, Collections.sort() uses TimSort
        List list = Arrays.asList(5, 2, 9, 1, 5, 6);
        Collections.sort(list);
    }
}

Use Cases

• Default choice for most sorting needs in Java
• Real-world data that often has some pre-existing order
• When stability is required

Radix Sort

Characteristics

• Time Complexity: O(nk) where k is the number of digits
• Stable: Yes
• In-place: Yes
• Space Complexity: O(n + k)

Implementation

public class RadixSort {
    public static void sort(int[] arr) {
        int max = getMax(arr);
        
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(arr, exp);
        }
    }
    
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
    
    private static void countSort(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        
        for (int i = 0; i < arr.length; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

Use Cases

• Sorting integers with a limited range
• Sorting strings with fixed-length keys
• When the number of digits is small compared to the number of elements

Algorithm Comparison

Best Practices

When to Use Each Algorithm

• Merge Sort: When stability and guaranteed O(n log n) performance are required
• Quick Sort: For general-purpose sorting when stability isn't required
• Heap Sort: When memory usage is a concern and stability isn't required
• TimSort: Default choice for most sorting needs in Java
• Radix Sort: For sorting integers or strings with fixed-length keys

Performance Considerations

• Consider the size of your dataset
• Evaluate memory constraints
• Check if stability is required
• Consider the nature of your data (pre-sorted, random, etc.)
• Profile your application to identify bottlenecks

Conclusion

Understanding the characteristics and implementations of different sorting algorithms is crucial for making informed decisions in your Java applications. Each algorithm has its strengths and weaknesses, and the best choice depends on your specific requirements for stability, space complexity, and performance characteristics.