Bubble Sort vs Merge Sort: Performance, Code & Complexity

Sorting is a fundamental operation in computer science. Choosing the right algorithm can dramatically improve performance. In this tutorial, we compare Bubble Sort and Merge Sort using Python, Big O analysis, and benchmarks.

1. Time Complexity Comparison

Algorithm	Best Case	Worst Case	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n)	Yes

2. Python Code Examples

Bubble Sort

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    

Merge Sort

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        merge_sort(L)
        merge_sort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    

3. Benchmarking Performance

Let’s compare execution time for sorting 1,000 random numbers:

import random, time

arr = [random.randint(1, 10000) for _ in range(1000)]

start = time.time()
bubble_sort(arr.copy())
print("Bubble Sort:", time.time() - start)

start = time.time()
merge_sort(arr.copy())
print("Merge Sort:", time.time() - start)
    

4. Visualizing Growth

Bubble Sort’s O(n²) curve grows steeply, while Merge Sort’s O(n log n) remains efficient even with large inputs. Use matplotlib to plot performance.

5. When to Use Each

• Bubble Sort: Simple to implement, good for small datasets or teaching.
• Merge Sort: Fast and scalable, ideal for large datasets and production use.

📬 Connect With Me

Have questions or want to share your benchmarks? Reach out:

• Email: benjaminkabula@gmail.com
• LinkedIn: linkedin.com/in/benjaminkabula
• Twitter/X: @benjaminkabula

Let’s grow together in tech, data science, and algorithm mastery!