Miracle Sort

Esoteric

Algorithms that are more conceptual, humorous, or illustrative of a theoretical point than for practical use.

Adaptive

Performance improves significantly on data that is already partially sorted.

In-Place

Requires a constant amount of extra memory space (O(1)), regardless of input size.

Stable

Preserves the relative order of elements with equal values.

Miracle Sort is a conceptual, esoteric algorithm based on the "generate and test" paradigm, where the "generate" step is to wait for an external, non-computational event—a miracle. It operates by continuously checking if the array is in sorted order. On an unsorted array, it will run in an infinite loop, perpetually waiting for the data to be sorted by some cosmic intervention or random hardware failure. Its only practical use is for educational or humorous purposes to illustrate the concept of a non-terminating algorithm.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

Miracle Sort is part of a family of "joke" algorithms, which includes Bogosort (a.k.a. Permutation Sort) and Quantum Bogosort.
It can be considered the most optimistic sorting algorithm, as it operates on pure faith.
The algorithm's performance can be significantly improved by increasing the user's desire for a sorted array.

How it Works

Assume the array is sorted.
Iterate through the array, comparing each element to the one before it.
If an element is found that is smaller than its predecessor, the array is not sorted. Stop the check and start over.
If the end of the array is reached without finding any out-of-order elements, a miracle has occurred! The array is sorted, and the algorithm can terminate.
If the array was not sorted, repeat the entire process from the beginning, ad infinitum.

Complexity Analysis

Best Case

O(n)

Average

O(\infty)

Worst Case

O(\infty)

Space

O(1)

Advantages

Simplicity: The implementation for checking if an array is sorted is extremely simple.
Adaptive: In the best-case scenario (an already-sorted array), it terminates in a single pass with $O(n)$ complexity.
No Computational Cost: The sorting process itself requires zero CPU cycles, as all the work is outsourced to a miracle.
Perfectly In-Place: It requires only $O(1)$ additional space and never modifies the array.

Disadvantages

Non-Terminating: For any unsorted array, the algorithm will never halt in a deterministic computational model.
Impractical: It is completely unusable for any real-world sorting task.
Relies on Miracles: Its success is dependent on external, undefined, and likely non-existent phenomena.

Implementation

JavaScript miracle-sort.js

function isArraySorted(arr) {
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      return false; // Found an inversion, not sorted
    }
  }
  return true; // No inversions found, sorted
}

function miracleSort(arr) {
  // Keep checking until a miracle happens.
  while (!isArraySorted(arr)) {
    // Wait for divine intervention...
  }
  return arr;
}