Sorting is used in almost any modern application and typically has a great impact on the overall application performance. Sorting algorithms differ by work time and some other factors like requirements of additional memory or dependence on the nature on sorted data. So, it may be difficult to decide which algorithm to choose in a certain case.
In practice, Quick Sort is usually the fastest sorting algorithm. Its performance is measured most of the time in O(N × log N). This means that the algorithm makes N × log N comparisons to sort N elements.
However, there are sorting algorithms that use fewer operations, for example Bucket Sort, whose performance is measured as O(N). According to Wikipedia and other sources, the performance of the Bucket Sort degrades with clustering; if many values occur close together, they will all fall into a single bucket and be sorted slowly.
Theoretically, since Bucket Sort uses fewer comparisons than Quick Sort, it should work faster. So, I decided to check this with AQtime. I created a simple C# application that sorts an array of integer values using the Quick Sort and Bucket Sort algorithms.
My implementation of the QuickSort and BucketSort are based on the code I found on the following web pages. I’d like to thank their authors for publishing the code to the Web:
To time my application, I used AQtime’s Performance profiler and the User + Kernel Time counter. First, I measured the execution time of the application sorting an array of 10,000 integers. I got the following results:
As you can see, the profiling results say that the Bucket Sort algorithm works slower than Quick Sort. To know what makes the BucketSort function slow I decided to profile it by lines.
I created a line level area, added the BucketSort function to it and ran profiling again. Once the results were generated, I selected the BucketSort function in the Report panel and switched to the Details panel. From the results displayed in the Details and Editor panels, I can see that the major portion of processing time is wasted on creating objects that serve as buckets, sorting data in them, and moving the sorted elements from the buckets to the resultant array.
Thus, although Bucket Sort requires fewer comparisons than Quick Sort, due to different overhead expenses it consumes much more time than expected.
Let’s try to get rid of these expenses. I modified the BucketSort function so that a number of buckets equals to the number of elements to be sorted and profiled the application again. I got the following results:
As you can see, now Bucket Sort works faster than Quick Sort. This corresponds to theory, but let’s check how Bucket Sort behaves with larger collections. I increased the number of the array’s elements to 300,000 and profiled the application again. This time, I was really surprised with the results: Bucket Sort was slower than Quick Sort --
From these results, I can draw a conclusion that Quick Sort is a good choice when you have to sort a lot of elements. When you are working with smaller collections, Bucket Sort may be a better choice.
In my example, I run two sorting procedures during the same profiling session. However, quite often it may be possible to use only one algorithm at a time. To find which algorithm is faster in this case, you can first profile the application when it is using one algorithm, then change source code and profile another algorithm, and then compare profiling results side-by-side:
If you are in doubt which algorithm to choose in your application (Quick Sort, Bucket Sort or some other), you can always use a performance profiler such as AQtime to decide which variant works better for you, and optimize your code further.