Can the Array be Unshuffled?

Question

Background

Very skilled card handlers are capable of a technique whereby they cut a deck perfectly in half, then perfectly interleave the cards. If they start with a sorted deck and perform this technique flawlessly 52 times in a row, the deck will be restored to sorted order. Your challenge is to take a deck of cards an integer array and determine whether it can be sorted using only Faro shuffles.

Definition

Mathematically, a Faro shuffle is a permutation on 2 n elements (for any positive integer n) which takes the element in position i (1-indexed) to position 2 i (mod 2 n+1). We would also like to be able to handle odd-length lists, so in that case, just add one element to the end of the list (a Joker, if you have one handy) and Faro shuffle the new list as above, but ignore the added dummy element when checking the list's order.

Goal

Write a program or function that takes a list of integers and returns or outputs  a truthy if some number of Faro shuffles would cause that list to be sorted in nondescending order (even if that number is zero--small lists should give a truthy). Otherwise,  return or output a falsy.

Examples

[1,1,2,3,5,8,13,21]  => True
[5,1,8,1,13,2,21,3] => True
[9,36,5,34,2,10,1] => True
[1,0] => True
[0] => True
[] => True
[3,2,1] => True
[3,1,2] => False
[9,8,7,6,5,4,3,2,1,0] => True
[9,8,7,6,5,4,3,2,0,1] => False
[3,1,4,1,5,9,2,6,9] => False
[-1,-1,-1,-2] => True

Scoring

This is code-golf so shortest source in bytes wins.

Answer 1

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

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

Answer 2

Pyth - 26 25 24 bytes

Uses cumulative reduce to apply Faro shuffle multiple times and keep all the results. Then, it maps through it and checks if they are invariant under sorting, then uses sum to check is any are true. Returns a positive or zero.

smSI-db.usC_c2NQsC.tc2Qb

Test Suite.