Optimizing Bubble Sort with Early Termination Using a Boolean Flag

Recently a reader shared an interview experience at Meituan where the interviewer asked him to write bubble sort on paper, catching him off guard despite his familiarity with the algorithm.

The article first presents a straightforward Java implementation of bubble sort:

public void bubbleSort(int[] source) {
    for(int i = source.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1])
                // swap omitted
                swap(source, j, j+1);
        }
    }
}

While functionally correct, the code can be optimized because once a pass makes no swaps the array is already sorted, and further passes are unnecessary.

The suggested improvement introduces a boolean flag that records whether any swap occurred during a pass; if no swap happens, the method returns early:

public void bubbleSort(int[] source) {
    boolean exchange;
    for(int i = source.length - 1; i > 0; i--) {
        exchange = false;
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1]) {
                swap(source, j, j+1);
                exchange = true;
            }
        }
        if(!exchange) return;
    }
}

This simple change reduces the best‑case time complexity to O(N) when the input is already sorted, while the worst‑case remains O(N²). The article also reflects on why interviewers still ask about classic algorithms: they test fundamental understanding and problem‑solving mindset rather than just memorization.

Finally, the author encourages readers to study classic data structures and algorithms thoroughly and to practice interview questions to avoid similar pitfalls.