J, 16 14 bytes

*/@:+&(=>./\)-

Try it online!

-2 thanks to Bubbler!

Based on akamayu's idea, but applies max-scan to both the input and its negation instead of applying max and min scans, which saves bytes in J vs APL.

JavaScript (ES6), 39 bytes

Returns a Boolean value.

a=>a.every(m=v=>(v>a?v:a=v)<m?a==v:m=v)

Try it online!

Commented

a =>        // a[] = input array, re-used as the lower bound
a.every(m = // m = upper bound, initially NaN'ish
  v =>      // for each value v in a[]:
  ( v > a ? //   if v is greater than the lower bound:
      v     //     use v directly
    :       //   else:
      a = v //     update the lower bound to v
  ) < m ?   //   if v is lower than the upper bound:
    a == v  //     success if the lower bound is equal to v
            //     failure otherwise (v is between the 2 bounds)
  :         //   else:
    m = v   //     update the upper bound to v (truthy)
)           // end of every()

K (ngn/k), 13 bytes

&/|/=/&\'\-:\

Try it online!

Returns a positive integer for truthy and 0 for falsy.

I don't think I've seen any other code with such high slash ratio :)

&/|/=/&\'\-:\    Input: x = a vector of positive integers
          -:\    negate and collect until convergence;
                   gives [x, -x] since x is nonempty and positive
      &\'\       "minimum scan each" until convergence;
                   if x is all-equal, becomes [[x, -x]];
                   otherwise [[x, -x], [cummin of x, cummin of -x]]
                   note that cummin of -x is -(cummax of x)
    =/           reduce by elementwise equality;
                   [x, -x] or [x == cummin of x, x == cummax of x]
  |/             reduce by max;
                   x or (x[i] == (cummin of x)[i] or (cummax of x)[i] for each i)
&/               reduce by min

K (ngn/k), 17 bytes

{&/(x=|\x)|x=&\x}

Every element must be the minimal (or the maximal) element of its prefix.

Try it online!

APL(Dyalog Unicode), 13 10 bytes ^SBCS

A direct translation of the ngn/k solution. -3 bytes thanks to @att.

⊢∧.∊⌈⍀,¨⌊⍀

Try it on APLgolf! (10 bytes)

(⊢=⌈⍀)∧.∨⊢=⌊⍀

Try it on APLgolf! (13 bytes)

Uiua, 14 13 bytes

Probably can be improved as I'm not so familiar with Uiua.

/↧↥=⟜\↧:=⟜\↥.

Try it on Uiua pad! (13 bytes)

/↧↥⊃(=⟜\↧)=⟜\↥

Try it on Uiua pad! (14 bytes)

Python, 45 bytes

f=lambda l:min(l)<l.pop()<max(l)or l and f(l)

Attempt This Online!

Returns flipped truth values: Falsey (empty list) for sortable and True for not sortable. Consumes the input list.

Haskell + hgl, 23 bytes

no uq<f'[gj,mx,mn]<<pxn

Attempt This Online!

Explanation

For each prefix determine the maximum, minimum and last elements. If any of these results in 3 unique values then fail otherwise pass.

• pxn all non-empty prefixes
• f' apply all functions in a list ...
• gj last
• mx maximum
• mn minimum
• no none is ...
• uq unique

If the result is unique it means that there is an element which has both a greater and smaller element before it, and thus that element cannot be inserted into the deque.

Alternative algorithm, 34 bytes

f x=fo$(zW ma.*eq=#=x.*flz x)mN ma

Attempt This Online!

Explanation

We check that every element of the input is either a cumulative minimum or a cumulative maximum.

• Take the cumulative minimum and maximum of the input.
• Zip each with the original list to determine the equal elements.
• Zip the two results together with or.
• Check that every element in the result is true.

Reflection

This seems pretty poor overall. The second submission is very long but can be improved in a lot of ways. I don't see any sensible way to shorten the first submission.

Part of why the alterntive is so much longer is it seems to be that the algorithm uses a lot of references to the input. (The most expanded version references the input 4 times!) This makes the glue pretty costly.

• lz ma and lz mN for cumulative maximum and minimum could have pre-composed variants.
• zW ma, zW mN, and zW eq could all also have shortcuts. Generally zW could have more shortcuts.
• I implemented jzW to zip and concat lists. I chose to generalize this to any monad, however we can see in the above that it would have been useful to have generalized to a monoid. I'll leave the existing version, but I should make a version which zips and then uses a monoid action to combine the values.

Nibbles, 13 nibbles (6.5 bytes)

?`*!`\$[`\@]:

Attempt This Online!

?`*!`\$[`\@]:   # full program
?`*!`\$[`\@]:$  # with implicit variable shown
?            $  # index of the input array in
 `*             # cartesian product of:
   !        :   #   zip together by concatenating elements:
    `\$[        #     scan over input by minimum
                #     (=cumulative minumum)
        `\@]    #     scan over input by maximum
                #     (=cumulative maximum)

Go, 119 bytes

import."slices"
func f(l[]int)bool{for i:=1;i<len(l);i++{if p,e:=l[:i],l[i];e>Min(p)&&e<Max(p){return 0>1}}
return 0<1}

Attempt This Online!

Uses the fact (pointed out by @akamayu) that each element must be either the minimum or the maximum of it and all elements before it.

05AB1E, 11 10 bytes

ηε{DyθÚÊ}P

-1 byte porting @JonathanAllan's Jelly answer

Outputs 1 if sortable; 0 if not.

Try it online or verify all test cases or see a step-by-step output.

Original approach:

δ.SÅlεÙg}3å

Outputs 0 if sortable; 1 if not.

Try it online or verify all test cases or see a step-by-step output.

Explanation:

η        # Get all prefixes of the (implicit) input-list
 ε       # Map over each prefix `y`:
  {      #  Sort it
   D     #  Duplicate this sorted prefix
    y    #  Push the current prefix `y` again
     θ   #  Pop and keep its last item
      Ú  #  Trim all leading/trailing occurrences of this value from the
         #  sorted copy
       Ê #  Check that the two lists are NOT the same
 }P      # After the map: product to check all were truthy
         # (after which this is output implicitly as result)

δ        # Apply double-vectorized on two times the (implicit) input-list:
 .S      #  Compare (-1 if a<b; 0 if a==b; 1 if a>b)
   Ål    # Pop and leave just the lower triangle of this matrix
     ε   # Map over each row of the lower triangle:
      Ù  #  Uniquify
       g #  Pop and push the length
     }3å # After the map: check whether there is a 3 in the list
         # (after which this is output implicitly as result)

Charcoal, 16 bytes

⬤θ№⟦⌊…θ⊕κ⌈…θ⊕κ⟧ι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if the deque can be sorted, nothing if not. Explanation: Port of JonathanAllan's Jelly answer.

 θ                  Input array
⬤                   All elements satisfy
      θ             Input array
     …              Truncated to length
        κ           Current index
       ⊕            Incremented
    ⌊               Minimum so far
           θ        Input array
          …         Truncated to length
             κ      Current index
            ⊕       Incremented
         ⌈          Maximum so far
   ⟦          ⟧     Make into list
  №                 Contains
               ι    Current element
                    Implicitly print

R, 30 bytes

\(x,`!`=cummin)any(x-!x&x+!-x)

Attempt This Online!

Port of @Unrelated String's first Jelly answer.

Outputs swapped TRUE/FALSE.

Slightly ungolfed:

\(x)any(x-cummin(x)&(-x)-cummin(-x))

Jelly,  7  6 bytes

ṢƤtƑ"ḋ

A monadic Link that accepts a list of positive integers and yields 0 (falsey) if sortable or a positive integer (truthy) if not.

Try it online!

How?

Check that each sorted prefix has its original rightmost element at one end.

ṢƤtƑ"ḋ - Link: list of positive integers, A
 Ƥ     - for each prefix:
Ṣ      -   sort
    "  - zip with E in A applying f(SortedPrefix, E):
   Ƒ   -   is invariant under?:
  t    -     trim any {E} from both sides of {SortedPrefix}
     ḋ - dot-product with {A}

Nekomata + -e, 6 bytes

pƆᵗ≤ᵗ≥

Attempt This Online!

This swaps truthy and falsy.

pƆᵗ≤ᵗ≥
p       Find a prefix of the input
 Ɔ      Split it into the last element and the rest
  ᵗ≤    Check that the last is less than at least one element of the rest
    ᵗ≥  Check that the last is greater than at least one element of the rest

JavaScript (Node.js), 41 bytes

x=>!x.some(p=q=t=>t<x[0]?p<(p=t):q>(q=t))

Try it online!

Optimized

JavaScript (Node.js), 64 bytes

f=([c,...x],...a)=>c?f(x,c,...a)|f(x,...a,c):!a.some(p=>c>(c=p))

Try it online!

Raw parse of question

Jelly, 8 bytes

«\ż»\Œpi

Try it online!

Feels a bit silly, but beats a couple better ideas I've had.

     Œp     Generate every list built by choosing from, at each position,
  ż         either
«\          the cumulative minima
   »\       or the cumulative maxima.
       i    Is the input in this list?

Jelly, 8 bytes

n«\×»\o⁼

Try it online!

n           Is each element not equal to
 «\         the smallest element so far?
   ×        Multiply those comparisons pairwise with
    »\      the cumulative maxima,
      o     then replace zeroes with corresponding elements of the input. 
       ⁼    Is this result equal to the input?

Vyxal, 9 bytes

ɖ∵?ɖ∴ZΠ$ḟ

Try it Online! Port of Unrelated String's Jelly answer, and a bit of a mess. I tried writing my own answer, but it was a byte longer.

       $ḟ # Is every element of the input
     ZΠ   # Either
ɖ∵        # A cumulative minimum
   ɖ∴     # Or a cumulative maximum
  ?       # Of the input?