A few years ago, I was reviewing a pull request from a junior developer who was building a custom log-analysis tool. He had decided that Collections.sort() was "too much magic" and wanted to implement his own QuickSort to show off his understanding of algorithms. It looked great on paper, but as soon as he ran it against a dataset that was already partially sorted, the entire JVM crashed with a StackOverflowError. He had picked the first element as the pivot every single time, turning his O(n log n) dream into an O(n²) nightmare that exhausted the stack. It was a humbling reminder that while we usually rely on Java's built-in sorting, knowing how these algorithms actually move data around is the only way to debug them when things go sideways.

The Simplicity and Slowness of Bubble Sort

I'll be honest with you: you will almost never use Bubble Sort in a production environment. It is the "Hello World" of sorting algorithms. However, it's the best way to visualize the concept of "swapping" and "passes." The core idea is that the largest element "bubbles up" to the end of the array with every full pass through the list.

public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // Swap elements
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

The problem here is the nested loop. If you have 10,000 items, you're potentially looking at 100 million comparisons. It's agonizingly slow. But notice the n - i - 1 logic; since each pass guarantees the largest remaining element is in its final place, we don't need to check the end of the array over and over again.

Stability and Reliability with Merge Sort

When you need a guarantee that your sort is "stable"—meaning two elements with the same value stay in their original relative order—Merge Sort is your go-to. I use this mental model: it's a "divide and conquer" strategy. You split the array in half recursively until you have lists of size one, and then you merge those lists back together in the correct order.

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);

        merge(array, left, mid, right);
    }
}

private void merge(int[] array, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] L = new int[n1];
    int[] R = new int[n2];

    System.arraycopy(array, left, L, 0, n1);
    System.arraycopy(array, mid + 1, R, 0, n2);

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            array[k++] = L[i++];
        } else {
            array[k++] = R[j++];
        }
    }
    while (i < n1) array[k++] = L[i++];
    while (j < n2) array[k++] = R[j++];
}

The trade-off here is memory. Unlike Bubble Sort, Merge Sort isn't "in-place." You're creating temporary arrays (L and R) during the merge process. If you're working with a massive dataset on a memory-constrained machine, this overhead can actually become a bottleneck.

Optimizing for Speed with Quick Sort

Quick Sort is generally the fastest general-purpose sort in practice, which is why variations of it power many standard libraries. Instead of splitting the array exactly in half, it picks a "pivot" and partitions the array so that everything smaller than the pivot is on the left and everything larger is on the right.

public void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int pi = partition(array, low, high);

        quickSort(array, low, pi - 1);
        quickSort(array, pi + 1, high);
    }
}

private int partition(int[] array, int low, int high) {
    // To avoid the StackOverflow issue I mentioned earlier, 
    // picking a random pivot or the middle element is much safer.
    int pivot = array[high]; 
    int i = (low - 1); 

    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    return i + 1;
}

The magic here is that Quick Sort works in-place. No extra arrays are needed, making it very cache-friendly. Just be careful with your pivot selection. If you always pick the last element and the array is already sorted, you hit that O(n²) worst-case scenario. In a real-world scenario, I'd recommend using a "median-of-three" strategy to pick the pivot.

📋 Practical Task

Exercise: Building a Stable Transaction Ledger Sorter

Imagine you are building a financial application. You have a Transaction class with two fields: double amount and long timestamp. Your goal is to sort these transactions by amount in ascending order. However, if two transactions have the exact same amount, they must remain in the order they were originally received (their original index in the list).

Your Task:

• Create a Transaction class with amount and timestamp.
• Implement a MergeSortLedger class that contains a method sortTransactions(Transaction[] transactions).
• You must use the Merge Sort algorithm to ensure the sort is stable.
• Write a main method that creates an array of transactions where at least two transactions have the same amount but different timestamps. Verify that the one that appeared first in the input array still appears first in the sorted array.