The Sorting Network

The larger island contains a parallel sorting network. The white paving stones represent nodes in the network, which should be linked using the lines shown in the diagram below. The network can be used to sort six people (perhaps by age or height) by having them stand on the six paving stones at the north end of the garden, and follow the lines until they meet someone at a double paving stone. The person with the smaller number goes to the left, and the larger to the right. Eventually the six should arrive at the southern end sorted into order. A more detailed explanation of this can be found at the Computer Science Unplugged web site.

A sorting network

Interestingly, the sorting network relates to binary numbers (and therefore the fountain) in that you can test the correctness of a sorting network by sorting only every combination of zeros and ones in the inputs. These combinations are the 2n binary numbers, which is a lot faster than the n! possible permutations of inputs.

Related Sites

Back to the Bridges of Friendship Garden Homepage

Modified: 11-Nov-1998