Why Bubble Sort Uses a Flag but Selection Sort and Merge Sort Usually Do Not

[Rajeev Bagra]

When learning sorting algorithms, many beginners notice something interesting:

• Bubble sort often uses a variable like did_swap
• Selection sort usually does not
• Merge sort also does not

Why?

The answer comes from how each algorithm decides whether sorting is complete.

Let’s deeply understand all three methods step by step.

---

1. Bubble Sort

Bubble Sort Code

def bubble_sort(L, detail=False):

    did_swap = True

    while did_swap:

        did_swap = False

        for j in range(1, len(L)):

            if L[j - 1] > L[j]:

                # swap adjacent elements
                L[j - 1], L[j] = L[j], L[j - 1]

                did_swap = True

                if detail:
                    print(L)

    return L

---

How Bubble Sort Works

Bubble sort repeatedly compares adjacent elements.

Example:

[8, 4, 1, 6]

Compare:

• 8 and 4 → swap
• 8 and 1 → swap
• 8 and 6 → swap

Largest values gradually “bubble” toward the end.

---

Why Bubble Sort Uses a Flag

The important question is:

How does bubble sort know when sorting is finished?

Bubble sort does not know beforehand how many passes are required.

So it needs a mechanism to detect:

“Did anything change during this pass?”

That mechanism is the flag:

did_swap

---

Understanding the Flag

At the beginning of each pass:

did_swap = False

This means:

“So far, no swaps happened.”

If a swap occurs:

did_swap = True

Now the algorithm knows:

“The list was not fully sorted yet.”

---

When Bubble Sort Stops

Suppose the list becomes:

[1, 2, 3, 4]

Bubble sort checks all adjacent pairs.

No swaps happen.

So:

did_swap = False

remains False.

Then:

while did_swap:

stops.

The algorithm knows the list is sorted.

---

Important Insight

The flag allows:

• early stopping
• avoiding unnecessary passes
• better performance on nearly sorted lists

Without the flag, bubble sort would continue making extra passes even after sorting finished.

---

---

2. Selection Sort

Selection Sort Code

def selection_sort(L, detail=False):

    for i in range(len(L)):

        smallest = i

        for j in range(i + 1, len(L)):

            if L[j] < L[smallest]:
                smallest = j

        # place smallest element in correct position
        L[i], L[smallest] = L[smallest], L[i]

        if detail:
            print(L)

    return L

---

How Selection Sort Works

Selection sort repeatedly:

1. Finds the smallest remaining element
2. Places it into its correct position

Example:

[8, 4, 1, 6]

First pass:

• smallest = 1
• place it at beginning

Result:

[1, 4, 8, 6]

Next pass:

• find smallest among remaining elements

And so on.

---

Why Selection Sort Does NOT Need a Flag

Selection sort already knows exactly how many passes it must perform.

Specifically:

for i in range(len(L)):

guarantees enough passes to place every element correctly.

There is no uncertainty.

So selection sort never needs to ask:

“Did anything change?”

It simply follows its fixed structure.

---

Key Difference from Bubble Sort

Bubble sort:

• keeps going until no swaps occur

Selection sort:

• performs a predetermined number of passes

That is why selection sort usually does not need a flag.

---

---

3. Merge Sort

Merge Sort Code

def merge_sort(L):

    if len(L) <= 1:
        return L

    middle = len(L) // 2

    left = merge_sort(L[:middle])
    right = merge_sort(L[middle:])

    return merge(left, right)


def merge(left, right):

    result = []

    i = 0
    j = 0

    while i < len(left) and j < len(right):

        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

---

How Merge Sort Works

Merge sort uses a divide-and-conquer strategy.

It:

1. Splits the list into smaller halves
2. Recursively sorts each half
3. Merges the sorted halves together

---

Why Merge Sort Does NOT Need a Flag

Merge sort does not repeatedly ask:

“Is the whole list sorted yet?”

Instead, the recursion structure guarantees sorting.

If:

• left half is sorted
• right half is sorted

then merging them correctly produces a sorted list.

No swap detection is needed.

No repeated checking is needed.

So no flag is required.

---

Deep Conceptual Difference

Bubble Sort

Bubble sort is reactive.

It repeatedly asks:

“Did I still find disorder?”

So it needs a flag.

---

Selection Sort

Selection sort is structured.

It says:

“I will place one element correctly per pass.”

No flag required.

---

Merge Sort

Merge sort is recursive.

It says:

“If smaller pieces are sorted, merging them will produce a sorted result.”

Again, no flag required.

---

Final Comparison Table

Algorithm	Uses Flag?	Reason
Bubble Sort	Yes	Must detect whether swaps occurred
Selection Sort	No	Fixed number of passes
Merge Sort	No	Recursive divide-and-conquer structure

---

Final Important Insight

The bubble sort flag is not just a random variable.

It is a way for the algorithm to answer an important question:

“Did this pass make any changes?”

If the answer becomes “no,” sorting is complete.

[Author]

Posts