JavaScript (Node.js), 78 bytes

f=(x,g=i=4)=>x.reverse().map((c,i)=>c<Math.max(...x)?++g:x[i]=0)|i?f(x,--i):!g

Try it online!

-2 bytes from Neil(may extra -1 or -2 if weaker output format)

Polynomial time

Charcoal, 26 bytes

Ｆ³«≔⮌θθＦＬθ¿⁼§θκ⌈θ§≔θκ⁰»¬⌈θ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for double dequer, nothing if not. Explanation: Assumes the correctness of @l4m2's polynomial time algorithm.

Ｆ³«

Repeat thrice.

≔⮌θθ

Reverse the array.

ＦＬθ

Loop over its indices.

¿⁼§θκ⌈θ

If this element is the maximum of those remaining, then...

§≔θκ⁰

... replace it with 0.

»¬⌈θ

If the array only contains 0s then the original array was double dequer.

Unfortunately MapCommand only updates the array at the end of the map, otherwise you could write something like this for 20 bytes:

Ｆ³«≔⮌θθＵＭθ∧⁻κ⌈θ껬⌈θ

29 bytes to support all integers:

Ｆ³«≔⮌θθＦ⮌Ｅθλ¿⁼§θκ⌊θ≔Φθ⁻μκ軬θ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for double dequer, nothing if not. Explanation: Assumes the correctness of @l4m2's polynomial time algorithm.

Ｆ³«

Repeat thrice.

≔⮌θθＦ⮌Ｅθλ

Reverse the array and then loop over its indices in reverse. (This is because I want to be able to remove elements as I go.)

¿⁼§θκ⌊θ

If this element is the minimum of those remaining, then...

≔Φθ⁻μκθ

... remove that element.

»¬θ

If the array is now empty then the original input was double dequer.

05AB1E, 20 bytes

".œειćRíì˜"D…D{QJ.Và

Port of @alephalpha's Nekomata answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Explanation:

".œειćRíì˜"           # Push this string
           D          # Duplicate it
            …D{Q      # Push string "D{Q"
                J     # Join the stack together: ".œειćRíì˜.œειćRíì˜D{Q"
                 .V   # Evaluate and execute as 05AB1E code (see below)
                   à  # Check if any is truthy by taking the flattened maximum
                      # (which is output implicitly as result)

.œ                    # Get all partitions of the (implicit) input-list
  ε                   # Map over each partition:
   ι                  #  Uninterleave it into two parts
    ć                 #  Head extracted
     R                #  Reverse the list of parts
      í               #  And also reverse each inner part itself
       ì              #  Prepend it back to the other part
        ˜             #  Flatten all of it to a single list
         .œειćRíì˜    #  Do the same for each of those inner lists
                  D   #   Duplicate each of those inner-most lists
                   {  #   Sort the copy
                    Q #   Check if the two are equal (aka it was already sorted)

Nekomata + -e, 14 bytes

o$2ᵑ{Jĭᵃjᵈ↔,}=

Attempt This Online!

o$2ᵑ{Jĭᵃjᵈ↔,}=
o               Sort the input
 $              Push the input again
  2ᵑ{       }   Apply the following function twice:
     J              Nondeterministically partition the input
                    e.g. [4,3,5,2,6,1] may become [[4,3],[5],[2],[6],[1]]
      ĭ             Uninterleave
                    e.g. [[4,3],[5],[2],[6],[1]] -> [[4,3],[2],[1]], [[5],[6]]
       ᵃj           Concatenate both parts
                    e.g. [[4,3],[2],[1]], [[5],[6]] -> [4,3,2,1],[5,6]
         ᵈ↔         Reverse the first part
                    e.g. [4,3,2,1],[5,6] -> [1,2,3,4],[5,6]
           ,        Join the two parts
                    e.g. [1,2,3,4],[5,6] -> [1,2,3,4,5,6]
             =  Check equality (comparing to the sorted input)

Elisp 226 bytes

(defun d(i r)(let((o(list(pop i))))(while(and i o)(let((n(pop i)))(if(<= n(car o))(setq o(cons n o))(if(>= n(car(last o)))(setq o(append o(list n)))(if r(progn(setq o(cons n o))(if(not i)(setq o(d o nil))))(setq o nil))))))o))

Try it online!

ungolfed:

(defun double-dequer-sort (input recursive)
  (let ((output (list (pop input))))
(while (and input output)
  (let ((next (pop input)))
    (if (<= next (car output))
    (setq output (cons next output))
      (if (>= next (car (last output)))
      (setq output (append output (list next)))
    (if recursive
        (progn
          ;; no idea whether to add to end or beginning here
          (setq output (cons next output))
          (if (not input)
          (setq output (double-dequer-sort output nil))
        )
          )
      (setq output nil)
      )
    )
      )
    )
  )
output
)
  )