Search code examples
sortingdeterministic

Which are the deterministic sorting algorithms with O(nlogn)?

Which are the deterministic sorting algorithms with O(nlogn)...? Only name few algorithms...

Solution

  • Merge sort and heap sort are the archetypal O(nlogn) examples and are deterministic. Quicksort is O(nlogn) in the average case but not usually in the worst case (which is O(n^2)). Quicksort is very often implemented with a randomized pivot, so it's not always deterministic.