The easiest way to work them is to make drawings using the visual representation described...

The easiest way to work them is to make drawings using the visual representation described in the text.

Write a recursive method to randomly shuffle the nodes of a linked list by modifying the links. Easy: Use quadratic time, constant extra space. Not so easy: Develop a divide-and-conquer algorithm that takes linearithmic time and uses logarithmic extra memory. See Exercise 1.4.40 for the “merging” step.

EXERCISE 1.4.40

Riffle shuffle. Compose a program to rearrange a deck of n cards using the Gilbert-Shannon-Reeds model of a riffle shuffle. First, generate a random integer r according to a binomial distribution: flip a fair coin n times and let r be the number of heads. Now, divide the deck into two piles: the first r cards and the remaining n – r cards. To complete the shuffle, repeatedly take the top card from one of the two piles and put it on the bottom of a new pile. If there are n1, cards remaining in the first pile and n2 cards remaining in the second pile, choose the next card from the first pile with probability n1 (n1 + n2) and from the second pile with probability n2 (n1 + n2). Investigate how many riffle shuffles you need to apply to a deck of 52 cards to produce a (nearly) uniformly shuffled deck.