Какова сложность сортировки в Go по памяти?

Question

[Роман Сарваров]

Всем привет!
Вычислительная сложность сортировки sort.Slice и sort.SliceStable составляет O(n log n), а какова сложность по памяти в обоих случаях?

Comments

[Виктор Кожухарь]

Я считаю, что наилучшим способом в данном конкретном случае будет банальный эксперимент. Он даст вам больше информации, чем любое жонглирование формулами.

Answer 1

[Данила]

sort.Slice использует алгоритм quicksort, сложность по памяти O(log n)
sort.SliceStable использут алгоритм mergesort, сложность которого соответственно O(n)

Comments

[jcmvbkbc]

алгоритм quicksort, сложность по памяти O(log n)

да ладно, O(1) всегда было у quicksort, откуда там логарифм?

[fenrir]

jcmvbkbc, вроде оба случая могут быть.
Если компилятор умеет оптимизировать хвостовую рекурсию, то O(1), если не умеет, то на хранение кадров стека уходит O(log N)

[jcmvbkbc]

fenrir, хотя нет, не точняк. В quicksort же два рекурсивных вызова, первому из них по-любому нужен стек.

[mayton2019]

Автор хочет сравнить sort.Slice и sort.SliceStable

Рискну предположить что *Stable будет чуть сложнее.

Кто-то же должен внести плату за стабильность

Хехе...