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


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


    // 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


    // 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


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

    Don't we need to sort and eliminate half of the answers...

    Suggested test case: `[9, 1, 1, 1, 1]`. My own algorithm failed on this input

  • Python 3, 38 42 39 bytes

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

    Try it online!

    -3 bytes thanks to @JoKing and @Quuxplusone

    39 bytes thanks to TFeld's observation that any permutation `!= sorted(t)` must be `> sorted(t)`.

  • R, 41 bytes


    Try it online!

    `is.unsorted` rather than `any(...)` would also be 41 bytes.

    This base method is 44 bytes as a recursive function, might be golfable: Try it online!

  • Python 2, 39 bytes

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

    Try it online!

  • Brachylog (v2), 6 bytes


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


    ≤₁ 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


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

    ≤₁ 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 the infinity *byte* is why you must go for the head and especially the jaw.

  • Perl 6, 30 bytes


    Try it online!

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


    $!={                         }    # 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!

  • Wolfram Language (Mathematica), 30 bytes

    #//.x_/;[email protected]!=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 yes of course...

    thought there could be some savings by using `OrderedQ`, but couldn't make it work

    @GregMartin I used `OrderedQ` in my very first approach (see edits)

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


    L->{               // Method with Integer-list as both parameter and return-type
    for(;; // Loop indefinitely:
    // 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


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

    @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!

    No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)

  • JavaScript (ES6),  49  48 bytes

    Saved 1 byte thanks to @tsh

    Removes every 2nd element.


    Try it online!

    `p++&1` -> `a^=1`

  • Ruby, 37 bytes

    ->r{r=r[0,r.size/2]while r.sort!=r;r}

    Try it online!

License under CC-BY-SA with attribution

Content dated before 7/24/2021 11:53 AM

Tags used