# 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] -> [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] -> [4]

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

# R, 41 bytes

x=scan();while(any(x-sort(x)))x=x[!0:1];x


Try it online!

• is.unsorted rather than any(...) would also be 41 bytes. – Giuseppe Mar 26 '19 at 13:14
• This base method is 44 bytes as a recursive function, might be golfable: Try it online! – CriminallyVulgar Mar 26 '19 at 13:57

# Python 3, 3842 39 bytes

q=lambda t:t>sorted(t)and q(t[::2])or t


Try it online!

-3 bytes thanks to @JoKing and @Quuxplusone

• 40 bytes – Jo King Mar 26 '19 at 12:16
• 39 bytes thanks to TFeld's observation that any permutation != sorted(t) must be > sorted(t). – Quuxplusone Mar 26 '19 at 15:47

# Python 2, 39 bytes

f=lambda l:l>sorted(l)and f(l[::2])or l


Try it online!

# Brachylog (v2), 6 bytes

≤₁|ḍt↰


Try it online!

This is a function submission. Input from the left, output to the right, as usual. (The TIO link uses a command-line argument that automatically wraps the function into a full program, so that you can see it in action.)

## Explanation

≤₁|ḍt↰
≤₁       Assert that {the input} is sorted {and output it}
|      Handler for exceptions (e.g. assertion failures):
ḍ     Split the list into two halves (as evenly as possible)
t    Take the last (i.e. second) half
↰   Recurse {and output the result of the recursion}


## Bonus round

≤₁|⊇ᵇlᵍḍhtṛ↰


Try it online!

The snap's meant to be random, isn't it? Here's a version of the program that choses the surviving elements randomly (while ensuring that half survive at each round).

≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁            Assert that {the input} is sorted {and output it}
|           Handler for exceptions (e.g. assertion failures):
⊇ᵇ         Find all subsets of the input (preserving order)
lᵍ       Group them by length
ḍht    Find the group with median length:
t      last element of
h       first
ḍ        half (split so that the first half is larger)
ṛ   Pick a random subset from that group
↰  Recurse


This would be rather shorter if we could reorder the elements, but whyever would a sorting algorithm want to do that?

• One byte per infinity stone. – djechlin Mar 26 '19 at 20:42
• @djechlin the infinity byte is why you must go for the head and especially the jaw. – user64742 Mar 28 '19 at 0:44

# Perl 6, 30 bytes

$!={[<=]($_)??$_!!.[^*/2].&$!}


Try it online!

Recursive function that removes the second half of the list until the list is sorted.

### Explanation:

$!={ } # Assign the function to$!
[<=]($_)?? # If the input is sorted$_                  # Return the input
!!                # Else
.[^*/2]         # Take the first half of the list (rounding up)
.&$! # And apply the function again  # C# (Visual C# Interactive Compiler), 76 bytes g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}  Try it online! # Java 10, 106 97 bytes L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}  -9 bytes thanks to @OlivierGrégoire. Try it online. Only leave the first halve of the list every iteration, and removes $$\\frac{n+1}{2}\$$ items if the list-size is odd. Explanation: L->{ // Method with Integer-list as both parameter and return-type for(;; // Loop indefinitely: L=L.subList(0,L.size()/2)){ // After every iteration: only leave halve the numbers in the list int p=1<<31, // Previous integer, starting at -2147483648 f=1; // Flag-integer, starting at 1 for(int i:L) // Inner loop over the integer in the list: f=p>(p=i)? // If a>b in a pair of integers a,b: 0 // Set the flag to 0 : // Else (a<=b): f; // Leave the flag the same if(f>0) // If the flag is still 1 after the loop: return L;}} // Return the list as result  • n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} is shorter using streams, but I haven't been able to figure out how to avoid the java.lang.IllegalStateException: stream has already been operated upon or closed error after returning the stream – Gymhgy Mar 26 '19 at 21:09 • @EmbodimentofIgnorance this happens because reduce is a terminal operation that closes the stream. You won't ever be able to call reduce twice on the same stream. You can create a new stream, though. – Olivier Grégoire Mar 27 '19 at 15:37 • 97 bytes – Olivier Grégoire Mar 27 '19 at 16:05 • @OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks! – Kevin Cruijssen Mar 27 '19 at 18:17 • No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;) – Olivier Grégoire Mar 28 '19 at 13:02 # Wolfram Language (Mathematica), 30 bytes #//.x_/;Sort@x!=x:>x[[;;;;2]]&  Try it online! @Doorknob saved 12 bytes • Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]). – Doorknob Mar 28 '19 at 3:40 • @Doorknob yes of course... – J42161217 Mar 28 '19 at 10:24 • thought there could be some savings by using OrderedQ, but couldn't make it work – Greg Martin Mar 29 '19 at 7:15 • @GregMartin I used OrderedQ in my very first approach (see edits) – J42161217 Mar 29 '19 at 9:19 # JavaScript (ES6), 49 48 bytes Saved 1 byte thanks to @tsh Removes every 2nd element. f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a  Try it online! • p++&1 -> a^=1 – tsh Mar 29 '19 at 8:11 # Ruby, 37 bytes ->r{r=r[0,r.size/2]while r.sort!=r;r}  Try it online! • 36 bytes recursively – Kirill L. Mar 26 '19 at 20:41 # 05AB1E, 8 7 bytes [Ð{Q#ιн  -1 byte thanks to @Emigna. Removes all odd 0-indexed items every iteration, so removes $$\\frac{n-1}{2}\$$ items if the list-size is odd. 7 bytes alternative by @Grimy: ΔÐ{Ê>äн  Removes the last $$\\frac{n}{2}\$$ items (or $$\\frac{n-1}{2}\$$ items if the list-size is odd) every iteration. Explanation: [ # Start an infinite loop: Ð # Triplicate the list (which is the implicit input-list in the first iteration) {Q # Sort a copy, and check if they are equal # # If it is: Stop the infinite loop (and output the result implicitly) ι # Uninterweave: halve the list into two parts; first containing all even-indexed # items, second containing all odd-indexed items (0-indexed) # i.e. [4,5,2,8,1] → [[4,2,1],[5,8]] н # And only leave the first part Δ # Loop until the result no longer changes: Ð # Triplicate the list (which is the implicit input-list in the first iteration) {Ê # Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey) > # Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted) ä # Split the list in that many parts н # And only leave the first part # (and output the result implicitly after it no longer changes)  • You can use ι instead of 2ä if you switch to a keep every other element strategy. – Emigna Mar 26 '19 at 12:07 • Alternative 7 using the "remove the last half" strategy: ΔÐ{Ê>äн – Grimmy Mar 29 '19 at 10:03 • @Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer? – Kevin Cruijssen Mar 29 '19 at 10:07 • Feel free to add it. – Grimmy Mar 29 '19 at 10:07 # TI-BASIC (TI-84), 474245 44 bytes -1 byte thanks to @SolomonUcko! Ans→L1:Ans→L2:SortA(L1:While max(L1≠Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans  Input list is in Ans. Output is in Ans and is implicitly printed out. Explanation: Ans→L1 ;store the input into two lists Ans→L2 SortA(L1 ;sort the first list ; two lists are needed because "SortA(" edits the list it sorts While max(L1≠Ans ;loop until both lists are strictly equal iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list ; removes (n+1)/2 elements if list has an odd length L2→L1 ;store the new list into the first list (updates "Ans") SortA(L1 ;sort the first list End Ans ;implicitly output the list when the loop ends  Note: TI-BASIC is a tokenized language. Character count does not equal byte count. • I think you can replace not(min(L1=Ans with max(L1≠Ans to save a byte. – Solomon Ucko Apr 1 '19 at 11:22 # Jelly, 7 bytes m2$⁻Ṣ$¿  Try it online! # Haskell, 57 55 bytes (thanks to ASCII-only) f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x


Try it online!

Original Code:

f x|or\$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x


Try it online!

Ungolfed:

f xs | sorted xs = f (halve xs)
| otherwise = xs

sorted xs = or (zipWith (>) xs (tail xs))

halve xs = take (length xs div 2) xs

• Welcome to PPCG! – Rɪᴋᴇʀ Mar 28 '19 at 5:20
• 56 – ASCII-only Mar 28 '19 at 5:38
• 57 :( – ASCII-only Mar 28 '19 at 5:44
• 55 – ASCII-only Mar 28 '19 at 5:55

# Gaia, 9 8 bytes

eo₌⟨2%⟩↻


Try it online!

Explanation:

e		| eval input as a list
↻	| until
o		| the list is sorted
⟨2%⟩  	| and take every 2nd element

# Octave, 49 bytes

l=input('');while(~issorted(l))l=l(1:2:end);end;l


Try it online! This was a journey where more boring is better. Note the two much more interesting entries below:

### 50 bytes

function l=q(l)if(~issorted(l))l=q(l(1:2:end));end


Try it online! Instead of the uninteresting imperative solution, we can do a recursive solution, for only one additional byte.

### 53 bytes

f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())


Try it online! Yep. A recursive anonymous function, thanks to @ceilingcat's brilliant answer on my question. An anonymous function that returns a recursive anonymous function by defining itself in its argument list. I like anonymous functions. Mmmmm.

# MATL, 11 bytes

tv1L)ttS-a


Try it online!

This works by removing every second item.

### Explanation

t      % Take a row vector as input (implicit). Duplicate
v      % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
% Do...while
1L)  %   Keep only odd-indexed entries (1-based, linear indexing)
t    %   Duplicate. This will leave a copy for the next iteration
tS   %   Duplicate, sort
-a   %   True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack

• Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5] – Falco Mar 26 '19 at 13:06
• @Falco Thanks! Corrected now – Luis Mendo Mar 26 '19 at 14:19

# Java (JDK), 102 bytes

n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}


Try it online!

• Time to try F# :) – aloisdg Mar 28 '19 at 14:35

# Husk, 6 5 bytes

1 byte saved thanks to Zgarb

ΩΛ<Ċ2


Try it online!

### Explanation

ΩΛ<Ċ2
Ω         Repeat until
Λ<         all adjacent pairs are sorted (which means the list is sorted)
Ċ2         drop every second element from the list

• This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11 – Mike Holler Mar 27 '19 at 20:11
• @MikeHoller github.com/barbuz/Husk/wiki/Codepage – Xan Mar 27 '19 at 22:51
• @MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage – Leo Mar 27 '19 at 22:53
• Thank you, I learned something today :) – Mike Holler Mar 28 '19 at 13:30
• Use Ċ2 instead of (←½ to save a byte. – Zgarb Apr 21 '19 at 7:58

# Julia 1.0, 30 bytes

-x=x>sort(x) ? -x[1:2:end] : x


Try it online!

Takes every second element of the array if not sorted.

• use an ASCII operator like - for 20 bytes. also we almost always don't count chars :| so it'd be nice if that was removed from the header – ASCII-only May 3 '19 at 10:11
• Changed that. Thanks for 2 bytes! – niczky12 May 3 '19 at 12:27

# C++ (gcc), 103 bytes

I can't comment, but I improved the version from movatica by reducing the includes, and using auto.

-2 Bytes: ceilingcat
-2 Bytes: ASCII-only

#include<regex>
auto f(auto l){while(!std::is_sorted(l.begin(),l.end()))l.resize(l.size()/2);return l;}


Try it online!

• any reason you can't just use l.size()/2? – ASCII-only May 3 '19 at 10:12
• Yes, it does not work that way :) – peterzuger May 6 '19 at 10:39
• what do you mean? returning a list of size (n+1)/2 or (n-1)/2 are both valid. hmm.... – ASCII-only May 6 '19 at 14:02
• Ohh oops did'nt see that thanks – peterzuger May 7 '19 at 6:07

# K (oK), 22 20 bytes

Solution:

{(*2 0N#x;x)x~x@<x}/


Try it online!

Iterate over the input until it's sorted... if it's not sorted take first n/2 items.

{(*2 0N#x;x)x~x@<x}/ / the solution
{                 }/ / lambda that iterates
<x   / indices that sort x ascending (<)
x@     / apply (@) these indices back to x
x~       / matches (~) x? returns 0 or 1
(       ; )         / 2-item list which we index into
x          / original input (ie if list was sorted)
#x            / reshape (#) x
2 0N              / as 2 rows
*                  / take the first one


Edits:

• -2 bytes thanks to ngn
• (.5*#x)#x -> *2 0N#x – ngn Jun 7 '19 at 23:07
• I considered doing 2 0N but assumed it would be longer (without testing), thanks! – streetster Jun 9 '19 at 17:56

# Crystal, 59 50 bytes

With Array#sort (59 50 bytes):

def f(a);while a!=a.sort;a.pop a.size//2;end;a;end


Try it online!

Without Array#sort (102 93 bytes):

def f(a);while a.map_with_index{|e,i|e>a.fetch i+1,Int32::MAX}.any?;a.pop a.size//2;end;a;end


Try it online!

# Japt, 10 9 bytes

£=ëÃæÈeXñ


Try it

£=ëÃæÈeXñ     :Implicit input of array U
£             :Map
=            :  Reassign to U
ë           :  Every second element, starting with the first
Ã          :End map
æ         :Get the first element that returns true
È        :When passed through the following function as X
e       :  Test for equality with
Xñ     :  X sorted


# VDM-SL, 99 bytes

f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])


Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int

A full program to run might look like this:

functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])


# Pyth, 10 bytes

.W!SIHhc2Z


Try it online here. This removes the second half on each iteration, rounding down. To change it to remove the first half, rounding up, change the h to e.

.W!SIHhc2ZQ   Q=eval(input())
Trailing Q inferred
!SIH        Condition function - input variable is H
SIH          Is H invariant under sorting?
!             Logical not
hc2Z    Iteration function - input variable is Z
c2Z      Split Z into 2 halves, breaking ties to the left
h         Take the first half
.W        Q   With initial value Q, execute iteration function while condition function is true

• Taking every other element of the list is shorter. Replace hc with %. This also lets you delete the trailing lambda variable Z and let Pyth fill it implicitly, for a total 2 bytes saved. – hakr14 Jun 9 '19 at 3:37

# C++ (gcc), 139137 116 bytes

-2 bytes thanx to ceilingcat, -21 bytes thanx to PeterZuger

#include<regex>
auto f(std::vector<int>l){while(!std::is_sorted(l.begin(),l.end()))l.resize(-~l.size()/2);return l;}


Resize the vector to its first half until it's sorted.

Try it online!

• Imports are rquired to be included in the byte count, so you have to add the includes – Gymhgy Apr 25 '19 at 21:18
• Thanx, i'll add them. – movatica Apr 25 '19 at 21:27

# Julia 1.0, 33 bytes

-a=issorted(a) ? a : -a[1:end÷2]


Try it online!

## Python 2, 52 bytes

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


nice!

# Husk, 7 bytes

ΩS=Oo←½


Try it online!

removes last half.