Квадратичное. При вставке каждого элемента в среднем отсортированная часть будет на треть состоять из 0, на треть и 1 и на треть и 2. Если текущий элемент 2, то вставка за O(1), если текущий элемент 1, то вы потратите i/3 операций. Если элемент 0, то 2/3i. В среднем i/3 операций на один элемент. Если просуммировать это от 1 до n, то получится n(n-1)/6. Значит общее количество операций O(n^2).