Geek Answers Handbook

Sort the first n integers in linear time and constant space

I am looking for an algorithm without comparison or comparison that can sort an array containing any permutation of the first n positive integers, which should be O (n) time complexity and O (1) space complexity.

Is there an existing algorithm that meets these specifications?

+7
sorting algorithm
source share
3 answers

If you have an array of size N with all integers from 1 to N, you can use the following O (N) algorithm (Note: arrays are based on 1 for this pseudocode so as not to introduce unnecessary complexity in explaining the algorithm):

  • Start with the first element of the array.
  • If its array index matches its value, go to the next.
  • If not, replace it with the value in the array index corresponding to its value.
  • Repeat step 3 until more swaps are required.
  • If not at the end of the array, go to the next element of the array, otherwise go to step 7
  • Go to step 2.
  • Done
+10
source share

Related MSD sorting in place

+2
source share

If you are sure that all integers are between 1 and N, you can use a sort count

+1
source share

More articles:


All Articles