Shell sort

Insert across a gap, then a smaller gap. A gapped swap can reverse two 2s before gap 1. Time depends on the gaps: often better than n squared, not O of n log n for sure.