# Performance Impact of Java HotSpot™ to Quick-Sort, Heap-Sort and Bubble-Sort Algorithm?

### BY MARKUS SPRUNCK

It is commonly assumed that Bubble-Sort is an extremely poor sort algorithm and gets really slow with larger number of input data. In the following a small Java implementation shows some Use Cases where Bubble-Sort can even be faster than Heap-Sort and/or Quick-Sort. One additional interesting aspect is the influence of the Java 7 HotSpot™ optimisations.

## Basics

The algorithms should show the following behavior:

Figure 3 depicts the measured performance of random data and this confirms the average case performance of the three implementations.

**Figure 3: measured run time depending of the number of data **

Within the given data range 1000 to 64000 the fitted O(n^1.1) is a good approximation for O(n log(n)) with just some percent deviation. So, all three implementations show the expected performance for random number input.

## Results

In the first depiction the run time of Bubble-Sort, Heap-Sort and Quick-Sort for eight Use Cases is shown.

It demonstrates that for presorted arrays the performance of Bubble-Sort can be as good or even better than the very fast implementations of Heap-Sort and Quick-Sort.

**Figure 1: Three sorting algorithms, without Java HotSpot™ **

Running the example program with the activated Java HotSpot™ the performance by at least a factor of ten. The performance improvements due to Java HotSpot™ are the highest for the Heap-Sort implementation. Profiling the running code from Java HotSpot™ shows that getter methods will be inlined and this saves especially for Heap-Sort a lot of overhead.

**Figure 2: Three sorting algorithms, with Java HotSpot™**

If just some values are unsorted in a "presorted" array, the Bubble-Sort implementation may be significantly faster than Heap-Sort and Quick-Sort.

Notice that there is a difference between the Use Case where the unsorted elements are at the beginning or at the end of the array. If you like to use Bubble-Sort, you should insert new elements at the start of the array or modify Bubble-Sort loops - the difference in performance may be huge.

## Recommendations

- For some cases Bubble-Sort is faster than Quick-Sort, e.g if you have a presorted list with just some unsorted values at the beginning of an array. If you measure the performance of an algorithm do it with and without Java HotSpot™ (VM option -Xint) . The difference can be high.
- It is always a good idea to measure your time critical implementation of algorithms to get more information about the actual behavior- sometimes you get unexpected insights.