## Who is faster? Running time comparison: Randomized Quicksort vs. Hybrid Sort

#### Background

As we may already by the name, quicksort is a very efficient method of sorting. However, there’s still some room for improvement to best avoid the worse case, such as a sorted array. The first solution we can use is to use a random privot instead of the start, mid or end position of the array. Further than that, we can use a hybrid sort rather than a pure recursive quicksort. The reason is that when we deal with a small array or data, sometimes it is faster to use an n^2 method than calling a function recursively.

Now, let me explain what do randomized quicksort and hybrid sort really mean in detail.

Randomized Quick Sort

• It sorts the sublist of the original list (from a low index to a high index)
• At each pass, it picks three random elements of the sublist, chooses the median of these three elements and uses it as a pivot. The median is the element in the middle (for example, if the three elements are 12, 7, 24, the median is 12). Such algorithm is called a randomized quicksort. The expected running time of a randomized quicksort is O(n log n).

Hybrid Sort

For large lists, quick sort tends to be the fastest general-purpose (comparison) sorting algorithm in practice. However, it runs slower than some of the Θ(n^2) algorithms on small lists. Since it’s a recursive divide and conquer algorithm, it needs to sort many small sublists. A hybrid sorting algorithm combines quick sort with insertion sort to make quick sort faster. Run quick sort as usual until the sublists become small (say, when a number of elements in a sublist are less than a certain threshold), and then use insertion sort to sort the small lists.

#### Code in Java

Randomized Quicksort

Hybrid Sort

#### Test Cases

In order to compare the actual running time of these two sorting methods, I created a couple of test cases:

1. A large array with 10000 integer elements
1. Sorted array
2. Reversely sorted array
3. Random array
2. A small array with 10 integer elements
1. Sorted array
2. Reversely sorted array
3. Random array

#### Test Result

I ran 10 times of the test in a row, and recorded the winner of each test as the result. Because the result here already showed a obvious conclusion at this point, I didn’t go further to do more test.

So, for each test case, the winning status are listed below, where R stands for randomized quick sort and H stands for hybrid sort:

``````       10000 elements                 10 elements
Sorted  Reversed  Random   |  Sorted  Reversed  Random
``````
1. ``````   H        H        H     |    H        H        H
``````
2. ``````   H        H        R     |    H        H        H
``````
3. ``````   R        H        H     |    H        H        H
``````
4. ``````   H        H        H     |    H        H        H
``````
5. ``````   H        H        H     |    H        H        H
``````
6. ``````   H        H        H     |    H        H        H
``````
7. ``````   H        R        H     |    H        H        H
``````
8. ``````   R        H        H     |    H        H        H
``````
9. ``````   H        H        H     |    H        H        H
``````
10. ``````   H        H        H     |    H        H        H
``````

#### Conclusion

According to the test result, we know that it’s obvious that hybrid sort has a dominant advantage over the randomized quicksort, no matter in a large or small array.

To be more specific, comparing hybrid sort(hybrid) and randomized quicksort(randomized), in a large sorted array, hybrid wins 8 times and randomized wins 2 times; in a large reversely sorted array, hybrid wins 9 times and randomized wins 1 time; in a large random array, hybrid wins 9 times and randomized wins 1 time. We know that hybrid can run faster than randomized in most cases, but randomized could be faster sometimes.

For a small array, we know that randomized will never win based on the tests I ran.

In conclusion, hybrid sort works well for us to improve the efficiency of our randomized quicksort method.