Explaining Bubble Sort, Quick Sort, and Merge Sort with the Strategy design pattern, complete with code, trade-offs, and a runnable demo.
───────────────────────────────────────────────────────────
TL;DR
– What: Strategy pattern decouples what you do (sorting) from how you do it (bubble/quick/merge).
– Why: Swap algorithms at runtime without changing client code; add new ones without touching callers.
– How: Define a SortStrategy interface, implement concrete strategies, and pass one into a SortContext.
Introduction
When you need sorting, the best algorithm depends on data size, distribution, and constraints. Hard-coding one approach couples your code to a specific choice. The Strategy pattern solves this by encapsulating each algorithm behind a common interface so you can switch behavior at runtime without if/elif chains or client changes.
1) Strategy Interface
All strategies share a single method: sort(data) -> List[int].
Code: Strategy interface
| from abc import ABC, abstractmethod from typing import List # Strategy Interface class SortStrategy(ABC): @abstractmethod def sort(self, data: List[int]) -> List[int]: pass |
2) Concrete Strategies
Bubble Sort (simple but slow)
| class BubbleSort(SortStrategy): def sort(self, data: List[int]) -> List[int]: result = data.copy() n = len(result) for i in range(n): for j in range(0, n – i – 1): if result[j] > result[j + 1]: result[j], result[j + 1] = result[j + 1], result[j] return result |
Time: O(n²) average/worst, Space: O(1) extra (on the copied list). Great for tiny inputs or teaching.
Quick Sort (fast average case)
| class QuickSort(SortStrategy): def sort(self, data: List[int]) -> List[int]: result = data.copy() self._quick_sort(result, 0, len(result) – 1) return result def _quick_sort(self, arr: List[int], low: int, high: int): if low < high: pi = self._partition(arr, low, high) self._quick_sort(arr, low, pi – 1) self._quick_sort(arr, pi + 1, high) def _partition(self, arr: List[int], low: int, high: int) -> int: pivot = arr[high] i = low – 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 |
Time: ~O(n log n) average, O(n²) worst with unlucky pivots; Space: ~O(log n) recursion stack.
Merge Sort (stable and predictable)
| class MergeSort(SortStrategy): def sort(self, data: List[int]) -> List[int]: result = data.copy() self._merge_sort(result) return result def _merge_sort(self, arr: List[int]): if len(arr) > 1: mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] self._merge_sort(left) self._merge_sort(right) i = j = k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: arr[k] = left[i]; i += 1 else: arr[k] = right[j]; j += 1 k += 1 while i < len(left): arr[k] = left[i]; i += 1; k += 1 while j < len(right): arr[k] = right[j]; j += 1; k += 1 |
Time: O(n log n) worst-case; Space: O(n) for temporary arrays; Stable ordering.
3) The Context: Pluggable Behavior
Code: SortContext
| class SortContext: def __init__(self, strategy: SortStrategy = None): self._strategy = strategy def set_strategy(self, strategy: SortStrategy): “””Change the sorting strategy at runtime””” self._strategy = strategy def execute_sort(self, data: List[int]) -> List[int]: “””Execute the sorting using the current strategy””” if not self._strategy: raise ValueError(“Strategy not set”) return self._strategy.sort(data) |
The context holds a reference to a strategy and delegates work without knowing the algorithm details.
4) Client Code: Switching Strategies on the Fly
Code: Client demo
| def main(): data = [64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 70] print(f”Original data: {data}\n”) sorter = SortContext() print(“Using Bubble Sort Strategy:”) sorter.set_strategy(BubbleSort()) print(f”Sorted: {sorter.execute_sort(data)}\n”) print(“Using Quick Sort Strategy:”) sorter.set_strategy(QuickSort()) print(f”Sorted: {sorter.execute_sort(data)}\n”) print(“Using Merge Sort Strategy:”) sorter.set_strategy(MergeSort()) print(f”Sorted: {sorter.execute_sort(data)}\n”) print(“Demonstrating dynamic strategy change:”) strategies = [ (“Bubble Sort”, BubbleSort()), (“Quick Sort”, QuickSort()), (“Merge Sort”, MergeSort()) ] for name, strategy in strategies: sorter.set_strategy(strategy) test_data = [5, 2, 8, 1, 9] sorted_data = sorter.execute_sort(test_data) print(f”{name}: {test_data} -> {sorted_data}”) if __name__ == “__main__”: main() |
This demonstrates runtime swapping—the core benefit of the Strategy pattern.
Also:
Sorting Smarter: A Gentle Walkthrough of the Strategy Pattern (with C# Code)
Why This Design Is a Win
– Open/Closed Principle: add new strategies (e.g., HeapSort) without modifying clients.
– Single Responsibility: each class focuses on a single algorithm—easier to read and test.
– Runtime flexibility: choose algorithms dynamically based on data size or shape.
Potential Enhancements
– Type generalization with generics and a key function (like Python’s built-in sorted).
– Expose metadata (e.g., is_stable=True for MergeSort).
– Auto-select strategy via heuristics (size, near-sortedness).
– Unit tests for each strategy and context behavior.
Conclusion
You now have a clean, extensible implementation of the Strategy pattern for sorting. It keeps your codebase modular, testable, and easy to evolve. Use this approach when you need pluggable algorithms or want to compare implementations side-by-side.
Source code download: https://github.com/chanmmn/python/tree/main/2026/strategypython?WT.mc_id=DP-MVP-36769
Chanmingman's Blog 