Эффективный алгоритм сортировки для почти отсортированного списка, содержащего данные о времени?

Название говорит само за себя. Я подозреваю, что лучше всего использовать сортировку вставками, поскольку она лучше всего подходит для данных, отсортированных в основном. Однако, поскольку я знаю больше о данных, есть шанс, что есть и другие виды, на которые стоит обратить внимание. Таким образом, другие важные фрагменты информации:

1) это данные о времени, что означает, что я, вероятно, мог бы создать эффективный хэш для упорядочения данных. 2) Данные не будут существовать одновременно. вместо этого я буду читать записи, которые могут содержать один вектор, десятки или сотни векторов. Я хочу выводить все время в течение 5-секундного окна. Поэтому возможно, что сортировка, которая выполняет сортировку по мере вставки данных, будет лучшим вариантом. 3) память не является большой проблемой, но скорость процессора может быть узким местом системы.

При этих условиях может ли кто-нибудь предложить алгоритм, который стоит рассмотреть в дополнение к сортировке вставками? Кроме того, как определить «в основном отсортировано», чтобы решить, какой вариант сортировки является хорошим? Что я имею в виду, так это то, как я смотрю на свои данные и решаю, что «это не так отсортировано, как я думал, может быть, сортировка вставками больше не лучший вариант»? Будем признательны за любую ссылку на статью, в которой рассматривается сложность процесса, которая лучше определяет сложность относительно степени сортировки данных.

Спасибо

Редактировать: спасибо всем за вашу информацию. На данный момент я буду использовать простую сортировку вставками или сортировку слиянием (в зависимости от того, что я уже написал заранее). Тем не менее, я попробую некоторые другие методы, когда они будут ближе к фазе оптимизации (поскольку для их реализации требуется больше усилий). Спасибо за помощь