Why don't they use O(n) algorithms in order to sort arrays?

The Bucket Sort, Count Sort & Radix Sort are algorithms which only take O(n) operations in order to sort an array. They require additional information, but it's not much of a problem because it's possible to find this information and the algorithms will stay O(n).

Yet, usally when people want to sort arrays, they usally use Quick Sort, Heap Sort or Merge Sort.

However, if the size of the array is big enough, the O(n) algorithms will be faster.

So why do people rarely use these algorithms?

Bucket Count and Radix sorts all require constraints on the data that tend to make them not nearly as general.

Also remember that performance should ALWAYS be driven by requirements, and that radable, maintainable, robust code is the "prime directive".

Therefore it only makes sense to consider these sorts if an application has been written and it is MEASURED that the sorting time is causing it to not meet (or be dangerously close to) a performance specification.

Too add to that, what is the difference in a .456 second algorithm and a .569 second algorithm? Nothing that you would ever notice (unless you called this algorithm a lot, which is silly to sort something over and over again :D ).

The reason people use quick sort is because it is quick and easy, and for most cases it works just fine. If your data set is HUGE and time is a large factor in your program, then of course you are going to need a faster algorithm. It all depends on the size of the problem. See gents, size does matter :rolleyes:.