Я разработал алгоритм сортировки NlgN, который я назвал «турнирной сортировкой» некоторое время назад, который находит выходные элементы по порядку (то есть начинается с поиска первого элемента, затем он находит второй элемент и т. Д.). Я не уверен, что это вполне практично, поскольку накладные расходы на ведение бухгалтерского учета превышают затраты на быструю сортировку, сортировку слиянием и т. Д., Но при сравнении с 1 000 000 случайных элементов счетчик сравнения фактически оказался ниже стандартной реализации быстрой сортировки библиотеки (хотя я уверен, как это будет с новыми).
Для целей моего алгоритма "оценка" каждого элемента - это количество элементов, которое, как известно, лучше. Первоначально каждый элемент имеет оценку 0. Когда сравниваются два элемента, лучший элемент добавляет к его оценке оценку другого элемента плюс один. Чтобы запустить алгоритм, объявите все элементы как «подходящие», и, пока остается более одного приемлемого элемента, сравните два приемлемых элемента с наименьшим количеством баллов и сделайте проигравшего «неприемлемым». После того, как все предметы, кроме одного, были объявлены непригодными, выведите один оставшийся предмет, а затем объявите приемлемым все предметы, которые этот предмет «побил».
Очередь приоритетов, необходимая для сравнения двух элементов с наименьшей оценкой, представляет собой несколько раздражающий уровень накладных расходов на бухгалтерию, но если бы кто-то сортировал вещи, которые стоило сравнить, алгоритм мог бы быть интересным.