CODEWITHSUNDEEP
algorithmsorting
fmunshi
fmunshi

Reputation: 415

Sort first n integers in linear time and constant space

I'm looking for a non-comparison or comparison based algorithm 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 fits these specifications?

Upvotes: 8

Views: 6673

Answers (3)

Michael Goldshteyn
Michael Goldshteyn

Reputation: 74410

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

  1. Start at the first array element.
  2. If its array index matches its value, go to the next one.
  3. If not, swap it with the value at the array index corresponding to its value.
  4. Repeat step 3, until no more swaps are necessary.
  5. If not at the end of the array, go to the next array element, otherwise go to step 7
  6. Go to step 2.
  7. Done

Upvotes: 15

anijhaw
anijhaw

Reputation: 9422

When you are sure that all integers are between 1 and N you can use counting sort

Upvotes: 1

user191776
user191776

Reputation:

In-place MSD radix sort

Upvotes: 2

Related Questions