Slow Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Slow Sort

A humorous sorting algorithm based on the "multiply and surrender" paradigm: recursively sorts halves, swaps the mid and end values to find the local max, and recurse again on the remaining prefix.

How it works

Slow Sort (or Slowsort) was published in 1984 by Andrei Broder and Jorge Stolfi. It is a joke algorithm designed to be as slow as possible while still eventually sorting correctly. Its logic operates on the "multiply and surrender" design pattern:

1. To sort the sub-segment from index \(i\) to \(j\):
2. **Left Half Recurse:** Sort the left half: `slowsort(A, i, mid)`.
3. **Right Half Recurse:** Sort the right half: `slowsort(A, mid + 1, j)`.
4. **Local Max Swap:** Compare the last elements of both halves: \(A[mid]\) and \(A[j]\). If \(A[mid] > A[j]\), swap them. This comparison guarantees that the overall maximum element of the range is placed at the end index \(j\).
5. **Surrender Recurse:** Now that the maximum element is correctly placed at \(j\), recurse on all elements except the maximum: `slowsort(A, i, j - 1)`.

Complexity

Interactive visualization

Pseudocode

procedure slowSort(A, i, j):
  if i >= j:
    return
    
  mid ← floor((i + j) / 2)
  slowSort(A, i, mid)
  slowSort(A, mid + 1, j)
  
  if A[mid] > A[j]:
    swap(A[mid], A[j])
    
  slowSort(A, i, j - 1)

JavaScript implementation

function slowSort(arr, i = 0, j = arr.length - 1) {
  if (i >= j) return arr;
  
  const mid = Math.floor((i + j) / 2);
  slowSort(arr, i, mid);
  slowSort(arr, mid + 1, j);
  
  if (arr[mid] > arr[j]) {
    [arr[mid], arr[j]] = [arr[j], arr[mid]];
  }
  
  slowSort(arr, i, j - 1);
  return arr;
}

Pros and cons

When (not) to use it

• Humorous demonstrations: Perfect for coding humor or testing if someone reads code before deploying it.
• Production / standard systems: Never! Bubble sort is a speed demon compared to Slowsort.