--AAAAABBBBB  #B's sort before A's, - is empty buffer
B-AAAAA-BBBB
BBAAAAA--BBB
BB-AAAAa-BBB  #A moved to a to make room
BBBAAAAa--BB
BBB-AAAaa-BB
BBBBAAAaa--B
BBBB-AAaaa-B
BBBBBAAaaa--
BBBBB-Aaaaa-
BBBBBaA-aaa-  #Each A ends up moving twice; O(1.5N), linear.
BBBBBa-aaaa-
BBBBBaa-aaa-
BBBBBaaa-aa-
BBBBBaaaa-a-
BBBBBaaaaa--  # Plus 1.0N if you want to shift the set
# back to the original address range:
--BBBBBaaaaa