# 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. – Unrelated String Mar 26 at 11:01
• Don't we need to sort and eliminate half of the answers... – Sumner18 Mar 26 at 14:32
• Suggested test case: [9, 1, 1, 1, 1]. My own algorithm failed on this input – Conor O'Brien Mar 26 at 21:03

# Clojure, 65 bytes

(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))


Try it online!

• 45? – ASCII-only Mar 28 at 6:36
• – ASCII-only Mar 28 at 6:42

# MATLAB, 57 bytes

Callable as f(a), where a=[1,2,3,4,5]

f=@(x)eval('while~isequal(sort(x),x);x=x(1:end/2);end;x')


Example of usage:

>> a = [1, 2, 4, 3, 5];
>> f(a)

a =
1     2


# Zsh, 51 bytes

56 (+5) to call the function, 47 (-4) if not a function, but saved as an executable with a proper #! header (replace the recursive f call with $0). 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++ – Expired Data Apr 2 at 14:35
• Thank you Expired Data. I'll try to do better next time – Qazi Fahim Farhan Apr 3 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!

@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 – ASCII-only May 6 at 14:02 • @ASCII-only for Rust, feature flags are not commandline arguments, but special syntax in the code itself. – NieDzejkob May 6 at 19:36 • Huh, no commandline option (like C# and Haskell) huh – ASCII-only May 7 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. – lirtosiast Jun 6 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 2, 52 bytes

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


nice!