merge_shuffle.c

// 以下為pseudo code，並非可執行的程式。
// 吃兩個_List**參數，並將第一個list的第一個元素移到第二個list開頭。
void move_first(_List** from, _List** to) {
  _List* moved = *from;
  *from = (*from)->next;
  moved->next = *to;
  *to = moved;
}

// 進入點。count為list的元素個數
_List* merge_shuffle(_List* list, int count) {
  int leftCount = (count+1) / 2;
  int rightCount = count / 2;
  _List* left = list;
  _List* right = split(list, leftCount);
  merge_shuffle(left, leftCount);
  merge_shuffle(right, rightCount);
  return merge(left, right);
};

_List* merge(_List* left, _List* right, int leftCount, int rightCount) {
  _List *result = NULL;
  while(leftCount || rightCount) {
    // (leftCount / totalCount) 的機率從左邊取一個元素，否則從右邊取一個元素。
    if (float(rand())/RAND_MAX < floor(leftCount) / (leftCount + rightCount)) {
      move_first(&left, &result);.
      --leftCount;
    } else {
      move_first(&right, &result);.
      --rightCount;
    }
  }
  return result;
}