**1.** Yes; equal elements are never moved across each other.

**2.** Yes. But the running time would be slower when equal elements are present, and the sorting would be just the opposite of stable.

**3.** The following eight-liner is conjectured to be the shortest `MIX`

sorting routine, although it is not recommended for speed. We assume that the numbers appear in locations 1, . . ., *N* (that is, `INPUT EQU 0`

); otherwise another line of code is necessary.

*Note:* To estimate the running time of this program, note that *A* is the number of inversions. The quantity *B* is a reasonably simple function of the inversion table, and (assuming distinct inputs ...

Start Free Trial

No credit card required