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] -&gt; [1, 2, 3, 4, 5]

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


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

// Removing every second item:
[1, 2, 4, 3, 5] -&gt; [1, 4, 5]


or:

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


or:

// Removing the last half of the list
[1, 2, 4, 3, 5] -&gt; [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -&gt; [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] -&gt; [1, 4, 3] -&gt; [4, 3] -&gt; [4]
Python 3, 38  42 39 bytes



q=lambda t:t&gt;sorted(t)and q(t[::2])or t


Try it online!

-3 bytes thanks to @JoKing and @Quuxplusone