Thanos sort is not a real sorting algorithm. It is a joke inspired by the Marvel villain who wiped out half of all life with a snap of his fingers to bring "balance" to the universe. The algorithm works the same way: if the array is not sorted, destroy half the elements. Repeat until what survives is in order, or until only one value is left standing.
It always terminates. It always produces sorted output. It also destroys most of your data. Perfectly balanced, as all things should be.
12 values. The universe is unbalanced.
0 comparisons · 0 removals
12 values. The universe is unbalanced.
- Comparing
- Snapping
- Survived
Code
- def thanos_sort(a):
- while not is_sorted(a):
- mid = len(a) // 2
- first = a[:mid]
- second = a[mid:]
- if is_sorted(first):
- a = first
- elif is_sorted(second):
- a = second
- else:
- a = random_half(a)
- return a
Press play and watch the array disintegrate. Try Sorted to see it bail out
immediately (zero snaps, all survivors), then Reversed to watch it eliminate
values until almost nothing is left. The difference is not about speed. It is
about how much data makes it out alive.
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(n) | Already sorted. One check, no snaps. All values survive. |
| Average | O(n log n) | Each snap does O(n) work; at most log₂(n) snaps. Most values do not survive. |
| Worst | O(n log n) | Same structure. Guaranteed to terminate when one element remains. |
| Space | O(n) | Copies of subarrays at each level. |
| Stable | No | Position-based elimination. The snap does not care about value. |
On paper the complexity looks almost reasonable. O(n log n) puts it alongside merge sort and quicksort. The difference is that those algorithms sort n values. Thanos sort eliminates values until what is left happens to be sorted. That is like solving a jigsaw puzzle by throwing away pieces until the remaining ones fit.
Step by step
- Check if the array is sorted. If yes, we are done. The survivors live.
- Split the array in half.
- If the first half is already sorted, keep it. The second half turns to dust.
- Otherwise, if the second half is sorted, keep it. The first half turns to dust.
- If neither half is sorted, pick one at random. The other turns to dust.
- Go back to step 1 with the surviving half.
The algorithm always terminates: each snap halves the array, so after at most ⌈log₂(n)⌉ snaps only one value remains. One value is trivially sorted. Victory through attrition.
Worked example
"Sorting" [5, 2, 4, 1]:
| Snap | Array before | Action | Array after |
|---|---|---|---|
| — | [5, 2, 4, 1] | Check: not sorted. The universe is unbalanced. | — |
| 1 | [5, 2, 4, 1] | First half [5, 2] not sorted. Second half [4, 1] not sorted. Snap the second half anyway. | [5, 2] |
| — | [5, 2] | Check: not sorted. Still unbalanced. | — |
| 2 | [5, 2] | First half [5] is one element. Trivially sorted. Keep it. | [5] |
| — | [5] | One survivor. Sorted by default. | [5] |
Two snaps. Three values eliminated. The "sorted" output is [5]. Technically
correct. Also completely useless.
When to use it
| Reach for it when | Avoid it when |
|---|---|
| You are writing a joke for a tech talk | You like your data |
| Code golf, where character count matters more than correctness | The input matters at all |
| You want to teach what "sorting" means by showing what it does not | Anyone is relying on the output |
| You need a guaranteed-terminating meme algorithm | Literally always in production, ever, for any reason |
The code
Every version below uses the "prefer a sorted half" strategy shown in the visualiser. If neither half is sorted, it picks the first half on odd snaps and the second on even snaps (a deterministic stand-in for the randomness Thanos would presumably use).
def is_sorted(a):
return all(a[i] <= a[i + 1] for i in range(len(a) - 1))
def thanos_sort(a):
snap = 0
while not is_sorted(a):
snap += 1
mid = len(a) // 2
first, second = a[:mid], a[mid:]
if is_sorted(first):
a = first
elif is_sorted(second):
a = second
elif snap % 2 == 1:
a = first
else:
a = second
return a
nums = [5, 2, 4, 1, 8, 3]
result = thanos_sort(nums)
print(result) # probably just [5] or something
Common questions
What is Thanos sort?
A joke sorting algorithm inspired by the Marvel villain Thanos. It repeatedly destroys half the elements in an array until what survives happens to be in order. Named after the character who snapped away half of all life in the universe to achieve 'balance'.
Does Thanos sort actually sort an array?
Technically yes. The output is always sorted. The catch is that most of your data is dead. An input of twelve values might finish with two survivors. Congratulations, those two are in order.
What is the time complexity of Thanos sort?
O(n log n) in comparisons: each snap checks whether the array and its halves are sorted (O(n) work) and there are at most log₂(n) snaps before one element remains. Impressive on paper, until you notice the output is missing most of the input.
Is Thanos sort stable?
No. Elements are eliminated in bulk based on position. Two equal elements in different halves have no guarantee of surviving together. The snap is indiscriminate.
Should I use Thanos sort in production?
Only if you also delete half your users' accounts for balance. It exists for code golf challenges, programming memes, and making people think about what 'sorting' actually means. Reordering. Not eliminating.
How is Thanos sort different from bogosort?
Bogosort shuffles randomly and checks, preserving all elements but potentially running until the heat death of the universe. Thanos sort always terminates in at most log₂(n) snaps, but murders your data to get there. Two joke algorithms, two opposite failure modes.
What happens if the array is already sorted?
One check, zero snaps. All values survive. This is the only input where Thanos sort behaves like a reasonable algorithm, and it is also the input where you did not need to sort anything.