Bogobogosort

Algorithm

Bogobogosort sorts a list of n elements by recursively applying Bogosort on progressively larger prefixes until everything is in order.

function bogobogosort(a):
  if a is sorted: return a
  k ← len(a) - 1
  # Sort the first k elements (recursively!)
  a[0:k] ← bogobogosort(a[0:k])
  # If the prefix is in order, keep going; otherwise reshuffle entire array
  if a[0:k] ≤ a[k]:
    return a
  else:
    shuffle(a)
    return bogobogosort(a)
      

Complexity

The expected running time is on the order of O(n!n)—a factorial of factorials—making it one of the slowest sorting algorithms ever conceived.

Visual Demo Controls

• Press "Shuffle" to scramble the bars and begin another round of hopelessness.
• The animation highlights the current prefix under consideration.

Implementation details live in games/js/demos.js.