Empirical comparison analysis intends to evaluate the performance of algorithms based on the system runtime. Many algorithms might possess the same asymptote complexity, but their performance might differ based on the size of the input vector. Empirical analysis is performed on the underlying assumption that the system properties and configuration remain the same for all the running algorithms under consideration.
Table 5.2 shows the system runtime for actual implementation of sorting algorithms measured using microbenchmark in R:
Table 5.2: Empirical comparison of sorting algorithms using system configuration of 2.8-GHz Intel i7 CPU running Windows. The system runtime is shown in milliseconds
The input used for empirical analysis is a random vector of integers of various lengths ranging from 10, 100, 1,000 to 10,000. The input for the best-case scenario is an increasing sorted vector of length 1,000. Similarly, the input for the worst-case scenario is a decreasing sorted vector of length 1,000. We can observe that the performance of some algorithms is agnostic of the best and worst-case input. The following are some takeaways from the preceding Table 5.2:
- Algorithms with asymptotic complexity of O(n2) perform poorly for large length of input vectors. Shell sort shows superior performance. Bubble sort shows the worst performance unless the input is a best-case (sorted).
- Among the algorithms with asymptote complexity O(nlog n), heap sort is the worst performer except in the best-and worst-cases due to overhead of class structure (heaps).
- Overall, radix sort shows a consistently good performance across all lengths of input vectors as compared to other algorithms.