я так понимаю дело не в сортировке, а в принципе? list.sort() не стоит предлагать?
я бы предложил использовать 2 списка, старый и новый.
количество итераций будет от "длинна списка" (если входной список будет строго возрастающим)до "длинна списка" в квадрате (если входной список будет строго убывающим).
