Can the Array be Unshuffled?
MATL, 41 bytes

itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx


The output is 1 or 0.

Explanation

i              % get input array
tn2\           % is size odd?
?              % if that's the case
  YNh          % concat NaN at the end
]              % end if
tn             % get size of input array
t1+:           % vector 1:n+1, where n is input size, so loop will be entered even with []
"              % for loop
  x[]2e!PY)    % delete result from previous iteration and do the shuffling
  ttZN~)       % remove NaN, if there's any
  tS=A         % check if array is sorted
  t.           % copy the result. If true, break loop
]              % end for
wx             % remove unwanted intermediate result


Example

&gt;&gt; matl itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx
&gt; [1,1,2,3,5,8,13,21]
1