0

I was recently asked to create an in-place sorting algorithm in an interview. The follow up was to code it up to make it faster than O(n logn), discuss the time complexity of every loop.

I understand that insertion sort, bubble sort, heap sort, quicksort, and shell sort are all in-place, however which of these can be modified to have better time complexity?

nerdyGuy
  • 306
  • 1
  • 9
  • 1
    Does this answer your question? [Generic and practical sorting algorithm faster than O(n log n)?](https://stackoverflow.com/questions/4973045/generic-and-practical-sorting-algorithm-faster-than-on-log-n) – Grismar Feb 12 '22 at 03:59
  • It's a trick question of sorts - there are algorithms that do better in specific circumstances, and perhaps your interviewer presented you with such a situation, in which case it helps to be aware of some algorithms like radix sort. – Grismar Feb 12 '22 at 04:00
  • I thought of radix sort, but that's not in-place. – nerdyGuy Feb 12 '22 at 04:05
  • o(n log n) is the lower bound for _comparison_ sorts. Any sort can be in-place. Not all sorts can be in-place and use only constant additional storage. But the standard definition of in-place allows O(n) additional storage. So radix sort and bucket sort are fine. Note that radix and bucket sorts can be done with only constant additional space if they're operating on linked lists. Finally the "O(n)" sorts are actually Omega(nk) where k is the key length. Comparisons may be able to compare keys of length k in much less than O(k). So key length can be a decider for what's actually faster. – Gene Feb 12 '22 at 04:16
  • The standard definition of an in-place algorithm does not allow O(n) additional storage. The usual limit is O(1) if we treat pointers and indices as taking constant space, or O(log n) if we treat an index into a length-n array as taking log(n) bits. – user2357112 Feb 12 '22 at 04:23
  • Sometimes people say an operation is "in place" when they mean that it mutates the original data structure instead of returning a new one, but regardless of whether you consider that usage correct, "in-place algorithm" means something stricter. – user2357112 Feb 12 '22 at 04:25

1 Answers1

0

A comparison based sort cannot be faster than O(nlogn). Since all the algorithms you mentioned are comparison based, none of them can have better time complexity. There are algorithms like bucket sort and radix sort that can achieve O(n) in some cases, namely if the input is uniformly distributed.

Tyler Liu
  • 989
  • 1
  • 6
  • 7
  • I think it's important to point out that the limit of O(n log n) for comparison sorts is based on a proof - it's not a matter of not having discovered the magic sorting algorithm yet. – Mark Ransom Feb 12 '22 at 16:38