Корректность и время работы линейного алгоритма разбиения массива “на месте” на три части: элементы меньше, равные и больше опорного

Было задание реализовать алгоритм, который делил бы "на месте" массив на три условных части. Элементы меньше v, равные v, больше v. При этом не важно, в какой последовательности между собой будут элементы в левой и правой частях. Время работы должно быть O(n).
Задание для меня оказалось не таким уж и простым. В итоге получился следующий код:
public static void buildArray(int v, int[] array) { int length=array.length; System.out.println("Сортируем по элементу: " + array[v]);
swap(array, 0, v); v=0; int position=0; for(int i=1; i < length; i++) { if(array[i] < array[v]) { swap(array, v+1, i); swap(array, v-position, v+1); v=v+1; } else if(array[i] == array[v]) { swap(array, v+1, i); position=position+1; v=v+1; } } }
Суть решения лежит в том чтобы выбранный нами элемент v поместить в начало массива и ко всем оставшимся элементам применить сравнение.
Если текущий элемент ниже array[v], значит поместить его сзади выбранного. Если оба (array[i] и array[v]) равны, значит поместить их рядом, при этом все элементы попадающие под первое сравнение будут перемещаться в область (v-position), где position инкрементируется от количества одинаковых v-элементов.
Тут два вопроса:
Корректен ли алгоритм? Предыдущие варианты решения могли сработать на 10 разных входных значениях, но были неисправными на 11, поэтому вопрос не лишен смысла. Равняется ли время работы O(n). Мы проходим по массиву один раз. Хватает ли этого чтобы утверждать оценку в O(n)?

Ответ

Алгоритм, судя по всему, правильный.
Доказательство. Инвариант: элементы с индексами 0 <= индекс < v - position из куска массива вплоть до i меньше разделяющего значения, элементы с индексами v - position <= индекс <= v равны ему. При этом v - position — индекс первого значения, равного разделяющему, а v индекс последнего (из рассмотренных).
В начале инвариант выполняется.
Если новый элемент меньше разделяющего значения, выполняется первая ветка, этот элемент перемещается на место сразу за группой [v - position .. v], а затем меняется с начальным элементом группы. В результате этот элемент оказывается перед группой, а группа «смещается» на один элемент вперёд. Продвигается v с сохранением инварианта.
Если новый элемент равен разделяющему значению, выполняется вторая ветка, этот элемент перемещается на место сразу за группой [v - position .. v], и эта группа увеличивается на 1 элемент (position=position+1; v=v+1;), включая новый элемент.
Если новый элемент больше разделяющего значения, инвариант также не нарушается.
В конце цикла нерассмотренных элементов не осталось, и согласно нашему инварианту, элементы массива обработаны правильно.

Каждая итерация цикла O(1), т. к. выполняется за ограниченной количество операций. Количество итераций O(n). Итого сложность алгоритма таки O(n)