# Implement the Thanos sorting algorithm

The sorting algorithm goes like this:

While the list is not sorted, snap half of all items (remove them from the list). Continue until the list is sorted or only one item remains (which is sorted by default). This sorting algorithm may give different results based on implementation.

The item removal procedure is up to the implementation to decide, but the list should be half as long as before after one pass of the item removal procedure. Your algorithm may decide to remove either the first half or the list, the last half of the list, all odd items, all even items, one at a time until the list is half as long, or any not mentioned.

The input list can contain an arbitrary amount of items (within reason, let’s say up to 1000 items), not only perfectly divisible lists of 2^n items. You will have to either remove (n+1)/2 or (n-1)/2 items if the list is odd, either hardcoded or decided randomly during runtime. Decide for yourself: what would Thanos do if the universe contained an odd amount of living things?

The list is sorted if no item is smaller than any previous item. Duplicates may occur in the input, and may occur in the output.

Your program should take in an array of integers (via stdin or as parameters, either individual items or an array parameter), and return the sorted array (or print it to stdout).

Examples:

// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]

// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] ->  // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half


[1, 2, 4, 3, 5] could give different results:

// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]


or:

// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed


or:

// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed


or:

// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> 

• Having a test case which actually requires multiple snaps for multiple different snapping algorithms would be very helpful. Mar 26, 2019 at 11:01
• Don't we need to sort and eliminate half of the answers... Mar 26, 2019 at 14:32
• Suggested test case: [9, 1, 1, 1, 1]. My own algorithm failed on this input Mar 26, 2019 at 21:03

## Python 2, 51 bytes

a=input()
while a!=sorted(a):a=a[:len(a)/2]
print a


nice!

# Pip-xp, 12 11 bytes

$<=a?afVUWa  Takes the list as a command-line argument in Pip list format, e.g. [1;2;4;3;5]. The -x flag makes sure this is treated as a list rather than a string, and the -p flag formats the output list in the same way. Try it here! (Pip Classic doesn't support the -x flag, but here's a simulated version: Try it online!) ### Explanation A recursive solution: $<=a?afVUWa
a         ; First argument (the list)
$<= ; Fold on <= (truthy if each element is <= the one after it) ? ; If truthy, return: a ; The list unchanged ; Otherwise, return: f ; The main function V ; called with the following arglist: UWa ; Unweave the list into two sublists of every other element  For example, UW[1;2;4;3;5] returns [[1;4;5];[2;3]]. This list is passed as the arglist to the recursive call, as if we had called f with the arguments [1;4;5] and [2;3]. Since our function only uses its first argument, though, this is equivalent to simply recursing with an argument of [1;4;5]. # Retina, 38 bytes \d+ * /(_+),(?!\1)/+,_+(,?)$1
_+
$.&  Try it online! Takes comma-separated numbers. Explanation: \d+ *  Convert to unary. /(_+),(?!\1)/+  Repeat while the list is unsorted... ,_+(,?)$1


... delete every even element.

_+

f(){[ "$*" = "${${(n)@}[*]}" ]&&<<<$@||f $@[0,#/2]}  Try it online! There is no "is-sorted" builtin in zsh, but there are some "sort-array" builtins. We use the parameter expansion flag n, but o or i would also work. We then have to use [*] and quote to induce joining. This is shorter than alternatives (like zipping them together and comparing pairwise). # C++ 17 , 589 bytes I used recursion to solve it. Submitted this solution in codeforces and got accepted. Btw, I still can't stop laughing! I mean seriously, Thanos sort! #include <bits/stdc++.h> using namespace std;int n, *a; int f(int start123, int end123){int start, end;start = start123; end = end123;if(start == end){ return 1; }int ret=0, temp=0;bool flag = true;for(int i=start; i<end; i++){ if(a[i]<=a[i+1]){ ret++; }else{ flag=false; break; } }int mid = (start+end)>>1; if(flag){ ret=ret+1; }else{ int a,b; a = f(start, mid);b = f(mid+1, end);ret = max( a, b );}return ret;}int main(int argc, char const *argv[]){ cin>>n;a = new int[n+10];for(int i=1; i<=n; i++){cin>>a[i];}int ans = f(1,n);cout<<ans<<"\n";if(!a)delete[] a;return 0;}  • Hi and welcome to PPCG, the criterion of this question is code-golf, that means we are trying to solve the problem in as few bytes as possible. Typically people will post the number of bytes for their answer along with the answer (so for yours: 1120 bytes), your aim should be to reduce this! May I recommend starting by removing all unneccesary whitespace, naming your variables with single characters and looking at tips for golfing in c++ Apr 2, 2019 at 14:35 • Thank you Expired Data. I'll try to do better next time Apr 3, 2019 at 6:26 # F# (.NET Core), 67 61 bytes let rec t l=if l=(List.sort l)then l else t l.[0..l.Length/2]  Try it online! # Perl 6, 32 bytes {($_,*[^*/2]...{[<=] @$_})[*-1]}  -2 bytes thanks to Jo King Try it online! # Perl 5-a, 50 bytes @b=sort{$a-$b}@F while"@b"ne"@F"&&($#F/=2);say"@F"


Try it online!

# Rust (2018 edition), 79 78 bytes

|v:&mut Vec<_>|while{let q=&mut v.clone();q.sort();q<v}{v.resize(v.len()/2,0)}


Try it online!

This will be golfable if slice::is_sorted gets stabilized, but right now the required feature flag offsets all gains.

• feature flags are free though :P - they just count as a separate language May 6, 2019 at 14:02
• @ASCII-only for Rust, feature flags are not commandline arguments, but special syntax in the code itself. May 6, 2019 at 19:36
• Huh, no commandline option (like C# and Haskell) huh May 7, 2019 at 1:09

# TI-Basic (TI-84), 2930 36 bytes

Ans->L₁
While 1<dim(L₁
If 0≤min(ΔList(L₁:Then
L₁
Return:End
iPart(.5dim(L₁->dim(L₁
End


Input and output are through Ans.

• L1 is not legal input; you need to either use Ans or write Input L1. Same for output, either Ans or display. Jun 6, 2019 at 6:50

# PHP, 86 bytes

function t($a){for(;$n=$a[+$i++];$l=$n)$f|=$n<$l;return$f?t(array_slice($a,$i/2)):\$a;}


Try it online!

# Python 3, 60 bytes

a=list(input())
while a!=sorted(a):a=a[0:len(a)//2]
print(a)


Try it online!

If it has to be a list:

a=[1,34,2,42,3,4,5,23,4,12,34,53,65]
while a!=sorted(a):a=a[0:len(a)//2]
print(a)


this one even has a self scrambling thingy!

import random
a=list(input())
random.shuffle(a)
while a!=sorted(a):a=a[0:len(a)//2]
print(a)


### Explanation:

a=list(input())       #ask for a string(that will be converted to a list)
while a!=sorted(a):   #while the actual sorted list *isn't* sorted,
a=a[0:len(a)//2]  #it now equals the first half of it.
print(a)              #print it out!

• Welcome to the site and nice first answer! I've edited it slightly so that other users can run and test your code, and that the formatting's fixed. One thing to note: list(input()) doesn't give you an actual list, it just converts the input string into a list (hence why the TIO link outputs ['[']. Changing it to eval(input()) works for no extra bytes: Try it online! Jan 3, 2021 at 23:04
• @cairdcoinheringaahing thanks! I doubt that this will win, but it was fun! Jan 3, 2021 at 23:56

# Factor, 50 bytes

[ [ dup [ <= ] monotonic? ] [ halves nip ] until ]


Try it online!

Removes the first half of the list, where the first half is shorter when there's an odd number of elements.