Your insertion sort scans downwards from the highest populated index, bumping elements up as it goes. Given that you have space on both sides, I'm surprised that you didn't start in the middle and pick a scan direction based on the comparison result there.