Three way unshuffle

Unshuffle.scala

// Deal a deck of cards into three piles.                                                                                                                                                                                                                                       

def unshuffle(cards: List[Int]): (List[Int], List[Int], List[Int]) = cards.length match {
  case 0 => (Nil, Nil, Nil)
  case 1 => (cards, Nil, Nil)
  case length =>
    val (left, right) = cards.splitAt(length / 2)
    val ((a, b, c), (d, e, f)) = (unshuffle(left), unshuffle(right))
    if (c.length == a.length) (a ::: d, b ::: e, c ::: f)
    else if (b.length == a.length) (a ::: e, b ::: f, c ::: d)
    else (a ::: f, b ::: d, c ::: e)
}
// This can be easily parallelized.
// However, computing list length takes linear time.

// Another way to do this to keep a count and
// use it to differentiate in the pattern match.
def unshuffleCount(cards: List[Int]): (List[Int], List[Int], List[Int], Int) = cards.length match {
  case 0 => (Nil, Nil, Nil, 0)
  case 1 => (cards, Nil, Nil, 1)
  case length =>
    val (left, right) = cards.splitAt(length / 2)
    val ((a, b, c, j), (d, e, f, k)) = (unshuffleCount(left), unshuffleCount(right))
    val i = (j + k) % 3;
    j match {
      case 0 => (a ::: d, b ::: e, c ::: f, i)
      case 1 => (a ::: f, b ::: d, c ::: e, i)
      case 2 => (a ::: e, b ::: f, c ::: d, i)
    }   
}

def unshuffle2(cards: List[Int]) = { 
  val (a, b, c, _) = unshuffleCount(cards)
  (a, b, c)
}

// scala> unshuffle(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
// res0: (List[Int], List[Int], List[Int]) = (List(1, 4, 7, 10),List(2, 5, 8),List(3, 6, 9))
//
// scala> unshuffle2(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
// res1: (List[Int], List[Int], List[Int]) = (List(1, 4, 7, 10),List(2, 5, 8),List(3, 6, 9))
//

// The bottom-up way to do the same is to
// create (List(x), Nil, Nil, 1) for all x in the input list
// and merging these 4-tuples in a similar fashion

// The general idea can be extended to n-way unshuffle (using macros if in scala)

// More great stuff here: http://vimeo.com/6624203