left = 1
right = n-1
last = n-1
/* основной цикл до тех пор пока границы
отсортированных с разных сторон отрезков
не пересекутся */
while left < right
/* проход снизу вверх */
for j = right downto 1
if x[j-1] > x[j]
swap(x, j-1, j)
last = j
/* Корректируем нижнюю границу
до которой уже все элементы получились
отсортироваными */
left = last + 1
/* проход сверху вниз */
for j = 1 to right
if (x[j-1] > x[j] )
swap(x, j-1, j)
last = j
/* Корректируем верхнюю границу
после которой уже все элементы получились
отсортироваными */
right = last - 1