Answer 8
The basic bubble sort requires N–1 modules to find the largest element, then N–2 modules to sort the remainder of the list, for a total delay of 2N–3. An alternate implementation of the bubble sort bubbles the smallest element to the head of the list, as shown below.

It turns out that you can perform both of these simultaneously, resulting in both the largest and smallest items in the list being identified, and leaving a list of N–2 items to be sorted.

This has the effect of moving modules from the end of the network back toward the beginning, putting their delays in parallel with other modules. This reduces the total delay to (N – 1) + (N/2 – 1) = 1.5N – 2.

Contributor: Dave Tweed

Published: January-2003