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

Scala, 84 bytes

def q(t:List[Int]):List[Int]=if(t==t.sorted)t else q(t.grouped(2).map(_.max).toList)

Try it online!

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.

Python 2, 51 bytes

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

nice!

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!

Jelly, 6 bytes

m⁻Ṣ$¿2

Try it online!

Very similar to Erik's existing answer, but I came up with this independently, and Erik's no longer active.

How it works

m⁻Ṣ$¿2 - Main link. Takes a list L on the left
    ¿  - Loop while the condition is false, updating L each time:
   $   -   Condition:
  Ṣ    -     L sorted
 ⁻     -     L ≠ L sorted
m    2 -   Body: Take every second element of L

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

Husk, 7 bytes

ΩS=Oo←½

Try it online!

removes last half.

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!

Julia 1.0, 33 bytes

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

Try it online!

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!

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

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.

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 tips question. An anonymous function that returns a recursive anonymous function by defining itself in its argument list. I like anonymous functions. Mmmmm.

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!

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.

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.

Perl 5 -a, 50 bytes

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

Try it online!

Gaia, 9 8 bytes

eo₌⟨2%⟩↻

Try it online!

Explanation:

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

C++ (gcc), 139 137 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!

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

Perl 6, 32 bytes

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

-2 bytes thanks to Jo King

Try it online!

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!

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

TI-BASIC (TI-84), 47 42 45 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.

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

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!

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.

Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).

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.

Try it online or verify some more test cases (or verify those test cases with step-by-step for each 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)

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

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

Wolfram Language (Mathematica), 30 bytes

#//.x_/;Sort@x!=x:>x[[;;;;2]]&

Try it online!

@Doorknob saved 12 bytes

Clojure, 65 bytes

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

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

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

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
}

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

There's already a C# answer, so I decided to try my hand on a Java answer.

Try it online!

Ruby, 37 bytes

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

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?

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

Jelly, 7 bytes

m2$⁻Ṣ$¿

Try it online!

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.

MATL, 11 bytes

tv`1L)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

Python 2, 39 bytes

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

Try it online!

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

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

R, 41 bytes

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

Try it online!

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!