Thanos Sort

Esoteric

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

Probabilistic

Uses random choices to reduce the probability of worst-case performance.

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.

The hardest choices require the strongest wills. This algorithm faces the reality of a disordered array and enacts a radical solution. It is not about rearranging elements, but about achieving a state of perfect balance through reduction. The process is random, dispassionate, and fair to all elements, regardless of their value. When it's done, half the data will still exist. A small price to pay for salvation.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

This algorithm asks the question: "What did it cost?" The answer is "Everything." (or, more accurately, about $1 - (1/2^k)$ of the data).
While this specific implementation is $O(n^2)$ due to memory shifting, a highly optimized version using a linear filter scan could theoretically reach $O(n)$ .
If the array reduces to a single element or becomes empty, it is considered perfectly balanced.

How it Works

Scan the array to check if it is currently sorted.
If the array is sorted, the work is done.
If disorder is found... Snap.
The Snap selects half of the current elements at random.
Delete the selected elements from the array instantly.
Repeat this process until balance is achieved, or the array is reduced to a single, trivial element.

Complexity Analysis

Best Case

O(n)

Average

O(n^2)

Worst Case

O(n^2)

Space

O(1)

Advantages

Decisive Action: Runs in linear time $O(n)$ , as the problem size is halved with each pass. Faster than any hero can manage.
Inevitable Success: It will always produce a sorted array, eventually.
Perfectly Balanced: As all things should be.

Disadvantages

The Cost: You could not live with your own failure. Where did that bring you? Back to me. This algorithm is lossy and will permanently delete data.
Unpredictable Survivors: "You will never know" which elements will survive the snap.
A Mercy, Not a Permutation: It violates the fundamental contract of sorting—to preserve the original set of elements.

Implementation

JavaScript thanos-sort.js

function thanosSort(arr) {
  const isSorted = (a) => {
    for(let i = 0; i < a.length - 1; i++) {
      if(a[i] > a[i+1]) return false;
    }
    return true;
  };

  while (!isSorted(arr)) {
    // Determine how many to remove
    const countToRemove = Math.floor(arr.length / 2);
    
    for (let i = 0; i < countToRemove; i++) {
      // Pick a random element to sacrifice for the greater good
      const targetIndex = Math.floor(Math.random() * arr.length);
      
      // Delete the chosen element
      arr.splice(targetIndex, 1);
    }
  }
  return arr;
}