Многие люди упоминают о теоретико-информационной Ω (n lg n), связанной с алгоритмами сортировки сравнений, которые нельзя нарушать в сортировках сравнения.( Этот более ранний вопрос исследует, почему это так.)
Однако, есть некоторые типы сортировок сравнения, которые, не нарушая O (n lg n) в среднем случае, могут бытьпоказано, что работает быстрее на входах, которые уже предварительно отсортированы в некоторой степени.Например, сглаживающая сортировка Дейкстры выполняется в O (n) на уже отсортированных входах с O (n lg n) поведением в худшем случае.Один из моих любимых сортов, декартово дерево , доказанно пользуется оптимальным преимуществом предварительной сортировки в нескольких метриках.Например, он может сортировать любую последовательность с постоянным числом увеличивающихся или уменьшающихся подпоследовательностей за время O (n), постепенно снижаясь до O (n lg n) в худшем случае.
На предмет отсутствияДля сравнения, есть некоторые известные, но хитрые алгоритмы сортировки целых чисел, которые превосходят O (n lg n) bynp, выполняя хитроумные трюки с битами.Самый известный алгоритм целочисленной сортировки - это рандомизированный алгоритм, который может сортировать по O (n √lg lg n), тогда как самый быстрый детерминистический алгоритм целочисленной сортировки выполняется за O (n lg lg n).Возможно, вы слышали, что радикальная сортировка работает в O (n), хотя технически это O (n lg U), где U - наибольшее значение в массиве для сортировки.
Короче говоря, нет, вы можете 'не намного лучше, чем O (n lg n), но вы можете сделать немного лучше, если знаете что-то о своих входных данных.