CODEWITHSUNDEEP
algorithmsortingtime-complexitybig-o
J.doe
J.doe

Reputation: 37

Sort a table in O(n) complexity

I have to sort a table (vector), the size of this table is n, and in this table there is distinct number from 0 to n-1. Is it possible to sort this table (with another table and without using a new table) ? The complexity of this sort should be in O(n)

Upvotes: 0

Views: 160

Answers (1)

OmG
OmG

Reputation: 18838

You can see your answer in the following paragraph from here:

As described, counting sort is not an in-place algorithm; even disregarding the count array, it needs separate input and output arrays. It is possible to modify the algorithm so that it places the items into sorted order within the same array that was given to it as the input, using only the count array as auxiliary storage; however, the modified in-place version of counting sort is not stable.[3]

Hence, it is possible (using in-place counting sort).

Upvotes: 1

Related Questions