Лучший способ сортировки для этого?

Question

Вопрос;

Вам необходимо отсортировать различные банковские операции по дате. Большинство из них в порядке (по дате), только несколько из них вышли из строя.

Какой алгоритм сортировки вы используете между сортировкой вставки, выбором сортировки и сортировки слияний, чтобы использовать тот факт, что массив почти сортирован?

Мой ответ (не уверен, если его правильно)

Предполагая, что N> = 5, я бы с Merge Sort с момента его средн. временная сложность была бы O (n * log n), которая была бы более эффективной, чем сортировка вставки O (n^2). Однако, поскольку несколько транзакций будут в одни и те же даты, сортировка вставки будет хорошим методом сортировки STABLE.

Какой из них лучше в этом случае? Слияние или сортировка вставки? Я в правильном направлении?

Answer 1

Вы должны выбрать сортировку вставки не из-за стабильности, а потому, что она адаптивна (см. here) и будет превосходить результат, потому что вход почти сортируется для начала.

Смысл этой «адаптивной» характеристики заключается в том, что элементы, которые уже установлены, обрабатываются в момент времени O (1), а элементы, очень близкие к их отсортированному положению, также могут рассматриваться как O (1) (до некоторого k расстояние).