Bogo Sort

Randomly shuffles the array, checks if it’s sorted, and repeats. The monkey with a typewriter approach.

0 elements

SpdSize50

>Ready — Bogo Sort

Code

// Bogo Sort: shuffle until sorted
// WARNING: Use a VERY small array size
function isSorted() {
  for (let i = 0; i < length - 1; i++) {
    if (compare(i, i + 1)) return false;
  }
  return true;
}

let attempts = 0;
while (!isSorted() && attempts < 100000) {
  for (let i = length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    swap(i, j);
  }
  attempts++;
}

// Bogo Sort: shuffle until sorted
// WARNING: Use a VERY small array size
function isSorted() {
  for (let i = 0; i < length - 1; i++) {
    if (compare(i, i + 1)) return false;
  }
  return true;
}

let attempts = 0;
while (!isSorted() && attempts < 100000) {
  for (let i = length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    swap(i, j);
  }
  attempts++;
}

Analysis

BEST O(n)

AVG O((n+1)!)

WORST O(∞)

SPACE O(1)

UNSTABLE

Bogo Sort (a.k.a. Stupid Sort, Monkey Sort) works by randomly shuffling the entire array, then checking if it happens to be sorted. If not, shuffle again. Average case is O((n+1)!) which means for 10 elements you’d expect ~40 million shuffles. For 15 elements, heat death of the universe. Use small arrays unless you have a lot of patience.

Edit in playground→