В чем преимущество использования алгоритма стабильной сортировки по сравнению с нестабильной сортировкой с использованием исходного индекса для разрешения связей?

Question

Алгоритмы стабильной сортировки работают медленнее, чем нестабильные. В качестве примера golang использует O(n*log(n)*log(n)) вызовы для замены элементов.

Если наша цель - сохранить исходный порядок элементов, почему бы не просто пронумеровать их все (O(n)), тогдавыполнить нестабильную сортировку (O(n*log(n))), используя исходный индекс, для разрешения случаев, когда сравнения равны.

Это кажется быстрее.

т.е. O(n) + O(n*log(n)) < O(n*log(n)*log(n))

Это правильно? Есть ли причины предпочитать стабильную сортировку?

Answer 1

За исключением эффектов кэша, стабильные сортировки обычно быстрее , чем нестабильные сортировки, когда им разрешено использовать дополнительную память.

Стабильная сортировка, на которую вы ссылаетесь из golang, не использует дополнительное пространство, поэтому он должен использовать более медленный алгоритм. Когда важно не использовать дополнительную память, вместо этого используются нестабильные сортировки, потому что в большинстве случаев они почти такие же быстрые и не требуют этого.

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

Answer 2

Вводная сортировка (быстрая сортировка + сортировка кучи, поэтому наихудшая временная сложность составляет O (n log (n)) для двух массивов (исходные данные + индексы для исходных данных) займет больше времени, чем сортировка слиянием, что не потребуетСортировка исходных данных + массив индексов.

Нестабильная быстрая сортировка примерно на 15% быстрее, чем сортировка слиянием. Сортировка двух массивов одновременно сделает это медленнее, чем сортировка слиянием. Основным недостатком сортировки слиянием является то, чтоон использует второй массив.Процессор с 16 регистрами, например, X86 в 64-битном режиме, сортировка с четырьмя путями выполняется примерно так же быстро, как и быстрая сортировка.