Временная сложность упрощенной 3-сторонней сортировки разделов

Ниже приведен мой алгоритм, который представляет собой упрощенный алгоритм трехстороннего разделения Дейкстры для общего списка:

static <T extends Comparable> void dutchSort(List<T> list, int left, int right) {
    if (left >= right) return;

    T pivot = list.get(left);

    // smaller - index of the last element smaller than pivot value
    // equal - index of the last element equal to pivot value
    // larger - index of the first element larger than pivot value
    int smaller = left-1, equal = left, larger = right;

    // before sorting is completed, 'equal' is the current value
    // much like 'i' in a for-loop
    // O(N) time
    while (equal < larger) {
        if (list.get(equal).compareTo(pivot) < 0)
            Collections.swap(list, equal, ++smaller);
        else if (list.get(equal).equals(pivot))
            equal++;
        else
            Collections.swap(list, equal, --larger);
    }

    // recursively sort smaller subarray
    dutchSort(list, left, smaller+1);

    // recursively sort larger subarray
    dutchSort(list, equal, list.size());
}

Это O(1) пространства, и я думаю, что O(N^N) времени, но я не уверен. В сообщении Toptal о 3-сторонней быстрой сортировке говорится, что это O (N^2), но разница в том, что мой алгоритм гораздо более наивен. Мой мыслительный процесс таков: цикл while занимает O(N) времени, и в худшем случае (все N элементов различны?) проблема разбивается на N подмассивов размера 1.

Я попробовал основную теорему, но не был уверен ни в одном из значений переменных. Я думаю, что количество подзадач равно 2, каждый рекурсивный вызов уменьшает проблему в 2 раза, а объединение подзадач требует O (1) работы.

Все это просто обоснованное предположение, и я, вероятно, довольно далеко, поэтому я действительно хотел бы строго решить временную сложность.

Верно ли время O(N^N)? И если да, то почему?

Спасибо большое :)