Implement the Thanos sorting algorithm

Question

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]

Answer 1

Python 2, 51 bytes

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

nice!

Answer 2

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].

Answer 3

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.

_+
$.&

Convert to decimal.

Answer 4

C (gcc), 66 bytes

Snaps off the second half of the list each iteration (n/2+1 elements if the length is odd).

Try it online!

Takes input as a pointer to the start of an array of int followed by its length. Outputs by returning the new length of the array (sorts in-place).

t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}

Ungolfed version:

t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
  l: // jump label, will be goto'ed after each snap
  for(i = 0; i < n - 1; ) { // go through the whole array …
    if(a[i] > a[++i]) { // … if two elements are in the wrong order …
      n /= 2; // … snap off the second half …
      goto l; // … and start over
    }
  }
  a = n; // implicitly return the new length
}

Answer 5

Clojure, 65 bytes

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

Try it online!

Answer 6

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

Answer 7

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).

Answer 8

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;}

Answer 9

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!

Answer 10

Perl 6, 32 bytes

{($_,*[^*/2]...{[<=] @$_})[*-1]}

-2 bytes thanks to Jo King

Try it online!

Answer 11

Perl 5 -a, 50 bytes

@b=sort{$a-$b}@F while"@b"ne"@F"&&($#F/=2);say"@F"

Try it online!

Answer 12

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.

Answer 13

TI-Basic (TI-84), 29 30 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.

Answer 14

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!

Answer 15

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!

Answer 16

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.