# Substitute Algorithm

> Replace the body of a function with a clearer or simpler algorithm that produces the same results.

- kind: technique
- category: composing-methods
- aliases: Replace Algorithm
- canonical: https://aipatterns.dev/refactoring/techniques/substitute-algorithm
- inspired-by: https://refactoring.guru/substitute-algorithm

## Problem

A function reaches its result through a convoluted path: nested loops, flags, manual bookkeeping. A simpler approach exists, perhaps a standard library call or a well-known algorithm, but the old code stays because nobody wants to touch it.

## Solution

**Write the new algorithm in a fresh body and swap it in, keeping the signature. Verify with tests that both produce identical results for the same inputs.**

## Before

```ts
function mergeBusyIntervals(slots: Interval[]): Interval[] {
  const result: Interval[] = [];
  const used: boolean[] = slots.map(() => false);
  for (let i = 0; i < slots.length; i++) {
    if (used[i]) continue;
    let start = slots[i].start;
    let end = slots[i].end;
    let changed = true;
    while (changed) {
      changed = false;
      for (let j = 0; j < slots.length; j++) {
        if (used[j] || j === i) continue;
        if (slots[j].start <= end && slots[j].end >= start) {
          start = Math.min(start, slots[j].start);
          end = Math.max(end, slots[j].end);
          used[j] = true;
          changed = true;
        }
      }
    }
    used[i] = true;
    result.push({ start, end });
  }
  return result.sort((a, b) => a.start - b.start);
}
```

## After

```ts
function mergeBusyIntervals(slots: Interval[]): Interval[] {
  const sorted = [...slots].sort((a, b) => a.start - b.start);
  const merged: Interval[] = [];
  for (const slot of sorted) {
    const last = merged[merged.length - 1];
    if (last && slot.start <= last.end) {
      last.end = Math.max(last.end, slot.end);
    } else {
      merged.push({ ...slot });
    }
  }
  return merged;
}
```

## Why

- The sort-then-sweep version is a known pattern that readers recognize in seconds.
- It runs in O(n log n) instead of worst-case O(n³).
- Fewer flags and indices means fewer places for off-by-one bugs.

## Steps

1. Make sure the function is as small as possible. Use [Extract Method](https://aipatterns.dev/refactoring/techniques/extract-method.md) to isolate the algorithm from unrelated work.
2. Pin the current behavior with tests, including edge cases: empty input, one element, touching boundaries, duplicates, unsorted input.
3. Write the new algorithm next to the old one (`mergeBusyIntervalsV2`). Run both on the same inputs, by test or by property-based comparison.
4. When they agree, replace the old body with the new one. Run the tests.
5. Delete the temporary copy.

## Watch out

- "Same results" includes ordering, mutation of inputs, handling of `null`, error types and rounding. The new version above copies each slot so it does not mutate the caller's array; check such details explicitly.
- Don't substitute when the old algorithm encodes a business rule you do not fully understand. Characterize it with tests first.
- Performance can get worse as well as better. Check large-input behavior if the function sits on a hot path.
- If several algorithms are all valid and must be selectable, that is a [Strategy](https://aipatterns.dev/design-patterns/strategy.md), not a substitution.
- There is no inverse; you can always substitute back.

## Related

- Fixes [Duplicate Code](https://aipatterns.dev/refactoring/smells/duplicate-code.md) when replacing hand-rolled code with a library call, and [Long Method](https://aipatterns.dev/refactoring/smells/long-method.md).
- [Extract Method](https://aipatterns.dev/refactoring/techniques/extract-method.md) isolates the algorithm first.
- [Strategy](https://aipatterns.dev/design-patterns/strategy.md) applies when you need several algorithms at once.

## Agent checklist

- [ ] Tests covering edge cases existed or were written before the swap.
- [ ] Old and new implementations were compared on the same inputs.
- [ ] Input mutation, output order and error behavior match.
- [ ] The signature did not change.
- [ ] The old implementation is deleted.