Это эквивалентно сортировке вставкой?

Допустим, у нас есть 0-индексированная последовательность S, берем S [0] и вставляем ее в то место в S, где следующее значение выше, чем S [0 ], а предыдущее значение меньше S [0]. Формально S [i] следует размещать в таком месте, где S [i-1]

В списке работает так:

Sorting [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 5, 4, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 0, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 1, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 3, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Got [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Поскольку каждый раз, когда элемент вставляется в список, может быть до (n-1) номеров в списке. быть перемещенным, и мы должны сделать это n раз, чтобы алгоритм работал за O (n ^ 2) раз.

У меня была реализация Python, но я как-то потерял ее. Попробую написать немного позже, но реализовать это довольно сложно. Есть идеи?

Реализация Python находится здесь: http://dpaste.com/hold/522232/ . Он был написан busy_beaver с reddit.com, когда он обсуждался здесь http: //www.reddit. com / r / compsci / comments / ejaaz / is_this_equivalent_to_insertion_sort /