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 ...