Insertion sort

Insert each new number into the already-sorted prefix. Equal is not larger, so the walk stops and equal numbers keep start order. Best case is n minus one comparisons; reversed numbers cost n times n minus one, over two.