Quicksort is O(n log n) on average, O(n^2) worst-case. Its performance is already due to the simplicity of its inner loop, so there isn''t much you can do to make a correctly implemented quicksort go faster. ''Simple'' multithreading won''t help, as the costs of spawning a new thread will dominate. And unless you have a multiprocessor system, the threads will have to share your one CPU anyway, adding context-switching costs to the mix. So, it''s really not worth it.

On the other hand, if you were using a real parallel machine (with independent CPU nodes and bus lines, not just a SMP system), there would indeed be techniques you could apply to make the sort go faster. A number of libraries are available for that purpose (e.g. OpenMP). Languages like Fortran even integrate parallel control flow statements (FORALL, WHERE).

So, in the end, you''re better off just using an existing quicksort (or hybrid sorting algorithms) implementation (C : qsort(), C++ : std::sort()), rather than worry overmuch over how to make it faster.

[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Actually, the fastest sorting algorithm is the insertion sort. O(n) best case. Of course, average and worst case are O(n^2), but if you know the behavior of what you are sorting sometimes insertion is the best. For example, the current game I''m working on sorts all the sprites based on bounding positions every frame so they are drawn in the proper order. Since most of the time the sprites will already be in order, or at worst one or two sprites are out of order, insertion sort is significantly faster than any other.

That''s why you have hybrid sorting routines which adapt their sorting algorithm to the data they''re given. Common sort() implementation use insertion sort for small ranges, where it actually is faster than quicksort, and use quicksort to break down larger ranges into smaller ones where insertion sort is used.

If you''re sorting using integers or floats as the keys, use the radix sort - it''s O(n) iirc. Radix Sort Revisited (http://codercorner.com/RadixSortRevisited.htm)

Different sorts are best for different things ...

Certain sorts will be very slow with very random data, others will be slow with pre-sorted data, and yet more will be slow with reverse sorted data (i.e. data which is in the reverse order to which it should be on a 1:1 basis).

Profile the code & tailor it to use an algorithm to suit your needs

Tom L

Quicksort is not effective for fewer than about 50 items, after that, its average performance actually begins to show, and yes, it is O(n*log(n))

MergeSort is somewhat more complex, and guarantees O(n*log(n)) time complexity and O(n) space complexity for ANY AND ALL inputs, and it generally isn't hard to code, but it's hard to optimize (a somewhat redundant algorithm). An exception, is bottom-up imlementations on linked lists, where mergesort really shines.

InsertionSort is linear in the number of inversions, so in the worst case (string is reverse-sorted to begin with) it is O(n^2). However, for partially sorted lists, it is VERY fast, and it is also extremely simple and robust.

HeapSort also guarantees O(n*log(n)) time complexity and O(n) space complexity. It is easy to implement on arrays, and is great if you'll be using the sorted set for something like a spatial sweep, because it is designed to provided lowest (or highest) element at each step.

RADIX sort is very very fast: O(n) for integers and strings, however, it's a little confusing to code.

RADIX' little brother is BucketSort, which is also O(n+h) and is used on discreet sets. h is the range of values that are in the set (so if you know you're sorting twenty integers from 17 to 37, then that's an ideal case because it's O(n+n)=O(n))

BubbleSort is the most awful algorithm you could hope to use. it is O(n^3), its only positive feature is that a single sweep will find you either the maximum value or the minimum value, so you can use it to find the highest or lowest few values if that's all your interested in. However, if you have about 1000 values, even this is too complex for you to use, in which case you should just go with heap-sort.

EDIT: confused bubble sort with quick sort

George D. Filiotis

I am a signature virus. Please add me to your signature so that I may multiply.

[edited by - symphonic on March 8, 2003 9:33:00 AM]