Insert sort should also be pretty fast for almost stored list, (and works better for not almost sorted).