Вставлять элементы не просто в конец, а используя Insertion sort: ищем ему место с левого конца и вставляем в нужное место.