quote:Original post by Neosmyle
I''m not sure what you are trying to say here, but cedric''s original post was completely correct:

quote:Original post by cedric
If your integers aren''t too big, and they aren''t repeated, you can make an array

int sortedints[MAX_VALUE];

and then use the value of the integers as indices into this array.

Umm... No, it wasn''t. He said to create an array and use the integers and indeces into the array, aka bucketsort. However, he also said that it would work as long as they "aren''t repeated". This is wrong. He is wrong for saying it. You are wrong for saying he is right for saying it.

This method clearly works for repeated data since the value of the data is intrinsic to the indice and isn''t stored. What is stored is the _number_ of integers that equal that indice.

- mongrelprogrammer

introspective or introsort does a quicksort but can determine whether the input is an (almost) worst case scenario and will then switch to an O(n*log(n)) algorithm (mergesort I think). This is what STLport''s std::sort does IIRC.

Regards,
Dirk Gerrits