[Question]
  [
A [Faro shuffle](https://en.wikipedia.org/wiki/Faro_shuffle) is a technique frequently used by magicians to "shuffle" a deck. To perform a Faro shuffle you first cut the deck into 2 equal halves then you interleave the two halves. For example
```
[1 2 3 4 5 6 7 8]
```
Faro shuffled is
```
[1 5 2 6 3 7 4 8]
```
This can be repeated any number of times. Interestingly enough, if you repeat this enough times, you will always end up back at the original array. For example:
```
[1 2 3 4 5 6 7 8]
[1 5 2 6 3 7 4 8]
[1 3 5 7 2 4 6 8]
[1 2 3 4 5 6 7 8]
```
Notice that 1 stays on the bottom and 8 stays on the top. That makes this an [outer-shuffle](https://en.wikipedia.org/wiki/Out_shuffle). This is an important distinction.
# The Challenge
Given an array of integers *A*, and a number *N*, output the array after *N* Faro shuffles. *A* may contain repeated or negative elements, but it will always have an even number of elements. You can assume the array will not be empty. You can also assume that *N* will be a non-negative integer, although it may be 0. You can take these inputs in any reasonable manner. The shortest answer in bytes wins!
# Test IO:
```
#N, A,                                              Output
1,  [1, 2, 3, 4, 5, 6, 7, 8]                        [1, 5, 2, 6, 3, 7, 4, 8]
2,  [1, 2, 3, 4, 5, 6, 7, 8]                        [1, 3, 5, 7, 2, 4, 6, 8]
7,  [-23, -37, 52, 0, -6, -7, -8, 89]               [-23, -6, -37, -7, 52, -8, 0, 89]
0,  [4, 8, 15, 16, 23, 42]                          [4, 8, 15, 16, 23, 42]
11, [10, 11, 8, 15, 13, 13, 19, 3, 7, 3, 15, 19]    [10, 19, 11, 3, 8, 7, 15, 3, 13, 15, 13, 19]
```
And, a massive test case:
```
23, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
```
Should output:
```
[1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69, 98, 28, 57, 86, 16, 45, 74, 4, 33, 62, 91, 21, 50, 79, 9, 38, 67, 96, 26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36, 65, 94, 24, 53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22, 51, 80, 10, 39, 68, 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20, 49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100]  
```
  
[Answer]
## vim, ~~62~~ ~~59~~ 54
```
qrma50%mb:norm@q<cr>ggqOjdd'apjma'b@q<esc>0"qDJ<C-a>D@"i@r<esc>xxdd@"
```
Wow. This is possibly the hackiest thing I've written for PPCG, and that's saying something.
Input is taken as N on the first line followed by the elements of the array, each on its own line.
```
qr         first, we're going to record the contents of the @r macro. this is
             the macro which does the faro-shuffle operation.
  ma       set the mark 'a at the beginning of the file
  50%      move to the 50% point of the file (i.e. halfway down)
  mb       set another mark here
  :norm@q  evaluate the recursive macro @q. we'll get to what that does later,
             but the interesting part here is that it's :norm@q instead of @q.
             this is because a recursive macro terminates at the end of the
             file, which means when @q terminates, @r would also abort, which
             would make calling it with a count impossible. running @q under
             :norm prevents this.
  gg       move back to the top of the file for the next iteration
q          end recording
O          now we're inserting contents of the @q macro, the recursive part
             we can't record it directly because it's destructive
  j        move to line directly below mark 'b (which was just set before @q)
  dd       delete this line and bring it...
  'ap      up after mark 'a (which starts on line 1, bringing the N/2th line
             directly below line 1, aka line 2)
  jma      replace mark 'a one line below this so that the next time we call
             'ap, the line from the second half is interleaved with the lines
             from the first half
  'b       jump back to mark 'b (remember, 'b is the last line of the first
             half of the file, originally reached via 50%)
  @q       call ourselves, causing the macro to run until hitting EOF
0"qD       delete this into register "q
J          delete the empty line that remains
<C-a>      here's another interesting bit: we want to run @r N times. but 0@r
             means "go to column 0, and then run @r once." so we have to
             increment the input number...
D@"        and then *that* many times...
  i@r        insert @r...
xx         ... and finally, delete two characters, which is the extra @r from
             the increment
dd         delete the sequence of @rs into the "" register...
@"         and run it!
```
I actually possibly found several vim bugs while writing this answer:
* recording macros is not possible within other macros (when setting their text manually, not with `q`) or within `:*map`s.
* `:let @a='<C-v><cr>'<cr>i<C-r>a` outputs two newlines, not one, for whatever arcane reason.
I might investigate those further later.
Thanks to [Dr Green Eggs and Ham DJ](https://codegolf.stackexchange.com/users/31716/dr-green-eggs-and-ham-dj) for 3 bytes!
[Answer]
# [05AB1E](http://github.com/Adriandmen/05AB1E), 5 bytes
Code:
```
F2äø˜
```
Explanation, input: `N`, `array`:
```
F      # Do the following N times
 2ä    # Split the array into 2 pieces
   ø   # Zip
    ˜  # Deep flatten
```
Uses the **CP-1252** encoding. [Try it online!](http://05ab1e.tryitonline.net/#code=RjLDpMO4y5w&input=NwpbLTIzLCAtMzcsIDUyLCAwLCAtNiwgLTcsIC04LCA4OV0).
[Answer]
# Python, ~~68~~ 57 bytes
```
f=lambda n,x:n and f(n-1,sum(zip(x,x[len(x)/2:]),()))or x
```
*Thanks to @Sp3000 for golfing off 11 bytes!*
Test it on [Ideone](http://ideone.com/Qv78Sp).
[Answer]
## Python 2, 59 bytes
```
def f(n,L):exec"l=len(L)/2;L=(L+L[1:]*~-l)[::l];"*n;print L
```
A different approach, slightly longer than the other Python answers. Only works for positive even numbers of elements.
e.g. for `1, [1,2,3,4,5,6,7,8]`, take the array and append `len(L)/2-1` copies of itself minus the first element, e.g.
```
[1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8]
```
Then take every `len(L)/2`th element.
```
[1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8]
 ^       ^       ^       ^       ^       ^       ^       ^
```
[Answer]
# Haskell, 62 bytes
```
0!a=a
n!a|s<-length a=(n-1)![a!!mod(div(s*i+i)2)s|i<-[0..s-1]]
```
Let *s* = 2·*t* be the size of the list. The *i*-th element of the new list is obtained by taking the [![enter image description here](https://i.stack.imgur.com/ZM1kJ.png)](https://i.stack.imgur.com/ZM1kJ.png)-th element of the old list, zero-indexed, modulo *s*.
Proof: if *i* = 2·*k* is even, then
                                         [![enter image description here](https://i.stack.imgur.com/s4ur9.png)](https://i.stack.imgur.com/s4ur9.png)
and if *i* = 2·*k* + 1 is odd, then
                        [![enter image description here](https://i.stack.imgur.com/7ZHnm.png)](https://i.stack.imgur.com/7ZHnm.png)
Thus the values used for indexing are 0, *t*, 1, *t* + 1, 2, *t* + 2, …
[Answer]
# J - 12 bytes
Adverb (!) taking number of shuffles on the left and the array to shuffle on the right.
```
/:#/:@$0,#^:
```
The J parser has [rules for writing tacit adverbs](http://www.jsoftware.com/help/dictionary/dicte.htm), but they have very low precedence: if you want to use a train of verbs as a left argument, you can omit an otherwise necessary set of parentheses. So the above is actually short for `(/:#/:@$0,#)^:`, which takes the number of shuffles on the left as an adverb, and then becomes a monadic function taking the array to shuffle on the right.
That said, we shuffle as follows. `#` is the length of the array, so `0,#` is a two element list: 0 followed by something nonzero. Then `#/:@$` replicates that into a list as long as the input array, and takes its **sort vector**.
The sort vector of a list is the information for how to sort the list: the (0-based) invdex of the smallest element, followed by the index of the next-smallest, and so on. For example, the sort vector of `0 1 0 1 ...` will thus be `0 2 4 ... 1 3 5 ...`.
If J were now to sort this sort vector, it would Faro-shuffle it; but that would be trivial, since we'd get `0 1 2 3 ...` back. So we use [dyadic `/:`](http://www.jsoftware.com/help/dictionary/d422.htm) to sort the input array **as if it were** `0 2 4 ... 1 3 5 ...`, which Faro-shuffles it.
Example usage below. Try it yourself at [tryj.tk](https://a296a8f7c5110b2ece73921ddc2abbaaa3c90d10.googledrive.com/host/0B3cbLoy-_9Dbb0NaSk9MRGE5UEU/index.html#code=2%20%28%2F%3A%23%2F%3A%40%240%2C%23%5E%3A%29%201%202%203%204%205%206%207%208)!
```
   1 (/:#/:@$0,#^:) 1 2 3 4 5 6 7 8
1 5 2 6 3 7 4 8
   f =: /:#/:@$0,#^:
   2  f  1 2 3 4 5 6 7 8
1 3 5 7 2 4 6 8
   7  f  _23 _37 52 0 _6 _7 _8 89   NB. "negative 1" is spelled _1
_23 _6 _37 _7 52 _8 0 89
   1  f  0 0 0 0 1 1 1              NB. odd-length lists
0 1 0 1 0 1 0
```
[Answer]
# Pyth - ~~8~~ 7 bytes
*saved 1 byte thanks to @issacg*
```
usCc2GE
```
[Try it online here](http://pyth.herokuapp.com/?code=usCc2GE&input=%5B1%2C+2%2C+3%2C+4%2C+5%2C+6%2C+7%2C+8%2C+9%2C+10%2C+11%2C+12%2C+13%2C+14%2C+15%2C+16%2C+17%2C+18%2C+19%2C+20%2C+21%2C+22%2C+23%2C+24%2C+25%2C+26%2C+27%2C+28%2C+29%2C+30%2C+31%2C+32%2C+33%2C+34%2C+35%2C+36%2C+37%2C+38%2C+39%2C+40%2C+41%2C+42%2C+43%2C+44%2C+45%2C+46%2C+47%2C+48%2C+49%2C+50%2C+51%2C+52%2C+53%2C+54%2C+55%2C+56%2C+57%2C+58%2C+59%2C+60%2C+61%2C+62%2C+63%2C+64%2C+65%2C+66%2C+67%2C+68%2C+69%2C+70%2C+71%2C+72%2C+73%2C+74%2C+75%2C+76%2C+77%2C+78%2C+79%2C+80%2C+81%2C+82%2C+83%2C+84%2C+85%2C+86%2C+87%2C+88%2C+89%2C+90%2C+91%2C+92%2C+93%2C+94%2C+95%2C+96%2C+97%2C+98%2C+99%2C+100%5D%0A23&debug=0).
[Answer]
# Jelly, ~~9~~ 7 bytes
2 bytes thanks to Dennis!
```
œs2ZFð¡
```
[Try it online!](http://jelly.tryitonline.net/#code=xZNzMlpGw7DCoQ&input=&args=WzEsMiwzLDQsNSw2LDcsOF0+Mg)
### Explanation
```
œs2ZFð¡  Main dyadic chain. Arguments: x,y
      ¡  Repeat the following y time:
œs2          Split into two.
   Z         Transpose.
    F        Flatten.
```
## Previous 9-byte version:
```
œs2ZF
Ç⁴¡
```
[Try it online!](http://jelly.tryitonline.net/#code=xZNzMlpGCsOH4oG0wqE&input=&args=WzEsMiwzLDQsNSw2LDcsOF0+Mg)
[Answer]
## JavaScript (ES6), ~~61~~ 51 bytes
```
(n,a)=>[...a].map((e,i)=>a[(i<<n)%~-a.length||i]=e)
```
Modifies the input array in place and returns a copy of the original array. If this is unacceptable, `&&a` can be suffixed to return the modified array. Only works for small values of `n` due to the limitations of JavaScript's integer arithmetic. ~~61~~ 60 byte recursive version that works with larger `n`, based on @Lynn's formula:
```
f=(n,a,l=a.length)=>n?f(n-1,a.map((_,i)=>a[(i*-~l>>1)%l])):a
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 11 bytes
```
w:"tn2/e!1e
```
*Thanks to @Dennis for a correction*
[**Try it online!**](http://matl.tryitonline.net/#code=dzoidG4yL2UhMWU&input=MjMKWzEsIDIsIDMsIDQsIDUsIDYsIDcsIDgsIDksIDEwLCAxMSwgMTIsIDEzLCAxNCwgMTUsIDE2LCAxNywgMTgsIDE5LCAyMCwgMjEsIDIyLCAyMywgMjQsIDI1LCAyNiwgMjcsIDI4LCAyOSwgMzAsIDMxLCAzMiwgMzMsIDM0LCAzNSwgMzYsIDM3LCAzOCwgMzksIDQwLCA0MSwgNDIsIDQzLCA0NCwgNDUsIDQ2LCA0NywgNDgsIDQ5LCA1MCwgNTEsIDUyLCA1MywgNTQsIDU1LCA1NiwgNTcsIDU4LCA1OSwgNjAsIDYxLCA2MiwgNjMsIDY0LCA2NSwgNjYsIDY3LCA2OCwgNjksIDcwLCA3MSwgNzIsIDczLCA3NCwgNzUsIDc2LCA3NywgNzgsIDc5LCA4MCwgODEsIDgyLCA4MywgODQsIDg1LCA4NiwgODcsIDg4LCA4OSwgOTAsIDkxLCA5MiwgOTMsIDk0LCA5NSwgOTYsIDk3LCA5OCwgOTksIDEwMF0K)
### Explanation
```
w         % Take the two inputs N and A. Swap them
:         % Generate [1 2 ... N]
"         % Repeat N times
  tn2/    %   Duplicate A. Number of elements divided by 2
  e       %   Reshape to that number of rows
  !       %   Transpose
  1e      %   Reshape to one row
          % End (implicit)
          % Display (implicit)
```
[Answer]
# J, ~~22~~ ~~19~~ 17 bytes
3 bytes [thanks to @Gareth](https://codegolf.stackexchange.com/a/6554/48934).
2 bytes thanks to [@algorithmshark](https://codegolf.stackexchange.com/users/5138/algorithmshark).
```
-:@#({.,@,.}.)]^:
```
### Usage
```
>> f =: -:@#({.,@,.}.)]^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8
```
Where `>>` is STDIN and `<<` is STDOUT.
## Previous 22-byte version:
```
({~[:,/@|:@i.2,-:@#)^:
```
### Usage
```
>> f =: ({~[:,/@|:@i.2,-:@#)^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8
```
Where `>>` is STDIN and `<<` is STDOUT.
[Answer]
# Mathematica 44 bytes
With 4 bytes saved thanks to @miles.
```
Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&
```
---
`Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles]` splits the list into two equal sublists and shuffles (`Riffle`s) them.
---
```
 Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@8, 1]
```
{1, 5, 2, 6, 3, 7, 4, 8}
---
```
Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@100, 23]
```
{1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69,
98, 28, 57, 86, 16, 45, 74, 4, 33, 62, 91, 21, 50, 79, 9, 38, 67, 96,
26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36, 65, 94, 24,
53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22,
51, 80, 10, 39, 68, 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20,
49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100}
[Answer]
# APL, ~~23~~ 21 chars
```
({⊃,/⍵(↑,¨↓)⍨2÷⍨⍴⍵}⍣N)A
```
Without the assumption (Thanks to Dennis) and 1 char shorter:
```
({{∊,⌿2(2÷⍨≢⍵)⍴⍵}⍣⎕)⎕
```
Try it on [online](http://tryapl.org/?a=%7B%u2283%2C/%2C%u233F2%282%F7%u2368%u2262%u2375%29%u2374%u2375%7D%u23633%u23738&run).
[Answer]
# java, 109 bytes
`int[]f(int[]a,int n){for(int x,q=a.length,d[];0<n--;a=d){d=new int[q];for(x=0;x<q;x++)d[(2*x+2*x/q)%q]=a[x];}return a;}`
Explanation:
There is a pattern to how the elements move when they are faro shuffled:
let x be the original index
let y be the new index
let L be the length of the array
* y is double x
* if x is greater than or equal to half of L then increment y
* keep y within the array's bounds
or as code: `y=(2*x+x/(L/2))%L`
This assumes that indicies start at 0. Here's the code further explained:
```
int[] faroShuffle( int[] array, int numberOfShuffles ) {
    //repeat the faro shuffle n times
    for( int index, length=array.length, destination[]; 0<numberOfShuffles--; array=destination ) {
        //new array to copy over the elements
        destination=new int[length];
        //copy the elements into the new array
        for( index=0; index<length; index++ )
            destination[(2*index+2*index/length)%length]=array[index];
        //at the end of each loop, copy the reference to the new array and use it going forward
    }
    return array;
}  
```
[see ideone for test cases](http://ideone.com/XaSBKg)
[Answer]
# Julia, ~~45~~ 42 bytes
```
a\n=n>0?reshape(a,endof(a)÷2,2)'[:]\~-n:a
```
[Try it online!](http://julia.tryitonline.net/#code=YVxuPW4-MD9yZXNoYXBlKGEsZW5kb2YoYSnDtzIsMiknWzpdXH4tbjphCgpmb3IgKG4sIGEpIGluICgKICAgICgxLCAgMTo4KSwKICAgICgyLCAgMTo4KSwKICAgICg3LCAgWy0yMywgLTM3LCA1MiwgMCwgLTYsIC03LCAtOCwgODldKSwKICAgICgwLCAgWzQsIDgsIDE1LCAxNiwgMjMsIDQyXSksCiAgICAoMTEsIFsxMCwgMTEsIDgsIDE1LCAxMywgMTMsIDE5LCAzLCA3LCAzLCAxNSwgMTldKSwKICAgICgyMywgMToxMDApCikKICAgIHByaW50bG4oYVxuKQplbmQ&input=)
### How it works
We (re)define the binary operator `\` for this task. Let **a** be an array and **n** a non-negative integer.
If **n** is positive, we shuffle the array. This is achieved by reshaping it into a matrix of **length(a) ÷ 2** rows and two columns. `'` transposes the resulting matrix, creating of two rows, then flattening the result with `[:]`. Since Julia stores matrices in column-major order, this interleaves the two rows.
Afterwards, we call `\` recursively with the shuffled **a** and **n - 1** (`~-n`) as arguments, thus performing additional shuffles. Once **n** reaches **0**, we return the current value of **a**.
[Answer]
## Pyke, 7 bytes
```
VDlec,s
```
[Try it here!](http://pyke.catbus.co.uk/?code=VDlec%2Cs&input=7%0A%5B-23%2C+-37%2C+52%2C+0%2C+-6%2C+-7%2C+-8%2C+89%5D)
```
V       - Repeat N times:
 D      -  a,b = a (2nd arg first time round)
  le    -  b = len(b)//2
    c   -  a = chunk(a,b)
     ,  -  a = zip(*a)
      s -  a = sum(a, [])
```
[Answer]
## Actually, 15 bytes
```
`;l½≈@│t)HZ♂i`n
```
[Try it online!](http://actually.tryitonline.net/#code=YDtswr3iiYhA4pSCdClIWuKZgmlgbg&input=WzEsMiwzLDQsNSw2LDcsOF0KNQ)
Explanation:
```
`;l½≈@│t)HZ♂i`n
`            `n  do the following n times:
 ;l½≈              push half the length of the array
     @             swap
      │            duplicate entire stack
       t)H         last L//2 elements, first L//2 elements
          Z♂i      zip, flatten each element
```
[Answer]
# Prolog, 116 bytes
```
a([],[[],[]]).
a([H,I|T],[[H|U],[I|V]]):-a(T,[U,V]).
f(X,0,X).
f(X,N,Y):-N>0,M is N-1,f(X,M,Z),a(Z,[A,B]),append(A,B,Y).
```
## Usage
```
?- f([1,2,3,4,5,6,7,8],2,X).
X = [1, 5, 2, 6, 3, 7, 4, 8] ;
false.
```
[Answer]
# [Perl 5](https://www.perl.org/) `-lan`, 52 bytes
```
$a=<>;@F=map@F[$_,@F/2+$_],0..$#F/2while$a--;say"@F"
```
[Try it online!](https://tio.run/##K0gtyjH9/18l0dbGztrBzTY3scDBLVolXsfBTd9IWyU@VsdAT09FGcgpz8jMSVVJ1NW1Lk6sVHJwU/r/39BAR8HQUEfBAkiZArExFFvqKAApczAJlrDkMjT8l19QkpmfV/xf19dUz8DQ4L9uTmIeAA "Perl 5 – Try It Online")
[Answer]
# PHP, 98 bytes
```
function($a,$n){while($n--)for($z=count($a)/2;$z;)array_splice($a,$z--,0,array_pop($a));return$a;}
```
[Try it online](http://sandbox.onlinephpfunctions.com/code/f45082b60e85e0514b5f1c8e59abe07398477e02).
]