Kata: Strategy Pattern

Table of contents

Problem Statement

Implement a Sorter that accepts different sorting strategies at runtime:

• Define a SortStrategy interface with a sort(data) method
• Implement at least three strategies: BubbleSort, InsertionSort, MergeSort
• The Sorter class accepts a strategy and delegates sorting to it
• Strategies can be swapped at runtime

Concepts

The strategy pattern encapsulates a family of algorithms behind a common interface, making them interchangeable. It replaces conditional logic (if/switch) with polymorphism.

When to use: When you have multiple algorithms for a task and want to select one at runtime without modifying the client code.

TypeScript: Interfaces define the strategy contract. See TypeScript Core Concepts.

PHP: Interfaces + first-class callables make strategies concise. See PHP Core Concepts and PHP 8.x Updates.

Python: Protocols provide structural typing for strategies. See Python Core Concepts.

Boilerplate

TypeScript

// strategy.ts
interface SortStrategy<T> {
  sort(data: T[]): T[];
}

class BubbleSort<T> implements SortStrategy<T> {
  sort(data: T[]): T[] { /* TODO */ return []; }
}

class InsertionSort<T> implements SortStrategy<T> {
  sort(data: T[]): T[] { /* TODO */ return []; }
}

class MergeSort<T> implements SortStrategy<T> {
  sort(data: T[]): T[] { /* TODO */ return []; }
}

class Sorter<T> {
  constructor(private strategy: SortStrategy<T>) {}

  setStrategy(strategy: SortStrategy<T>): void { /* TODO */ }
  sort(data: T[]): T[] { /* TODO */ return []; }
}

Hints

Solution

TypeScript

interface SortStrategy<T> {
  sort(data: T[]): T[];
}

class BubbleSort<T> implements SortStrategy<T> {
  sort(data: T[]): T[] {
    const arr = [...data];
    let swapped: boolean;

    do {
      swapped = false;
      for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
          [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
          swapped = true;
        }
      }
    } while (swapped);

    return arr;
  }
}

class InsertionSort<T> implements SortStrategy<T> {
  sort(data: T[]): T[] {
    const arr = [...data];

    for (let i = 1; i < arr.length; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }

    return arr;
  }
}

class MergeSort<T> implements SortStrategy<T> {
  sort(data: T[]): T[] {
    if (data.length <= 1) return [...data];

    const mid = Math.floor(data.length / 2);
    const left = this.sort(data.slice(0, mid));
    const right = this.sort(data.slice(mid));

    return this.merge(left, right);
  }

  private merge(left: T[], right: T[]): T[] {
    const result: T[] = [];
    let i = 0;
    let j = 0;

    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        result.push(left[i++]);
      } else {
        result.push(right[j++]);
      }
    }

    return [...result, ...left.slice(i), ...right.slice(j)];
  }
}

class Sorter<T> {
  constructor(private strategy: SortStrategy<T>) {}

  setStrategy(strategy: SortStrategy<T>): void {
    this.strategy = strategy;
  }

  sort(data: T[]): T[] {
    return this.strategy.sort(data);
  }
}

// Usage
const sorter = new Sorter(new BubbleSort<number>());
sorter.sort([3, 1, 4, 1, 5]); // [1, 1, 3, 4, 5]

sorter.setStrategy(new MergeSort<number>());
sorter.sort([3, 1, 4, 1, 5]); // [1, 1, 3, 4, 5]

Python

from typing import Protocol

class SortStrategy[T](Protocol):
    def sort(self, data: list[T]) -> list[T]: ...

class BubbleSort[T]:
    def sort(self, data: list[T]) -> list[T]:
        arr = data[:]
        n = len(arr)
        for i in range(n):
            swapped = False
            for j in range(n - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    swapped = True
            if not swapped:
                break
        return arr

class Sorter[T]:
    def __init__(self, strategy: SortStrategy[T]) -> None:
        self._strategy = strategy

    def set_strategy(self, strategy: SortStrategy[T]) -> None:
        self._strategy = strategy

    def sort(self, data: list[T]) -> list[T]:
        return self._strategy.sort(data)

Complexity Analysis

Cross-Language Notes

Python: Since Python uses duck typing, you don’t strictly need an interface — any object with a sort method works. The Protocol class makes this explicit for type checkers. You can also use plain functions as strategies thanks to first-class functions.

PHP: With first-class callables (PHP 8.1+), strategies can be as simple as $sorter->setStrategy(sort(...)). For more complex strategies, interfaces + classes remain the idiomatic approach.

Functional alternative: In functional programming, the strategy pattern is simply “passing a function”. Languages with first-class functions (all three here) can use closures instead of classes for simple strategies.