Эффективный функциональный вид

Question

Я программирую функцию для TI-Nspire , поэтому я не могу использовать встроенные функции внутри функции. Каков наиболее эффективный алгоритм сортировки списка чисел без изменения самого списка? (рекурсия и разбиение списка - это честная игра, как и обычное математическое использование.)

Answer 1

Mergesort является простым, простым, эффективным и стабильным: разбить список, выполнить рекурсивную сортировку и объединить результаты.

Чтобы быть более конкретным, сортировка слиянием принимает O (N log N), что является асимптотически оптимальным. Кроме того, на практике (с обоими алгоритмами, измененными для сортировки коротких подсписков со специальной сортировкой), mergesort может быть близким конкурентом модифицированной быстрой сортировке, используемой в стандартных библиотеках C / C ++.

Редактировать: в отличие от сортировки на месте, такой как быстрая сортировка и сортировка вставкой, сортировка слиянием требует вспомогательной памяти и проще всего реализовать путем копирования, а не замены.

Answer 2

Timsort используется в python и java SE 7. Для этого требуется лучшее из сортировки слиянием и сортировки вставкой. Сортировка вставкой - O (n ^ 2), но с небольшими списками чисел это быстрее, чем сортировка слиянием!

Таким образом, вы можете использовать это как общий алгоритм сортировки, как указано здесь