You could have the inner code:
    (a) shift the "higher third" values without doing comparisons
    (b) only have the data comparisons happen on the "middle third"
           and if you got to the end of that range without inserting,
           to simply insert at that point