Improving the Performance of Quicksort for Average Case through a Modified Diminishing Increment Sorting

Abstract

This paper presents an Improved Median-of-Three Sort which uses a modified diminishing increment sorting to efficiently sort elements that have the characteristics average case scenarios.
The improved medium-of-three sort was coded and implemented using C++ and Dev C++ compiler respectively. The results of the implementation and experimentation of this approach compared with Quicksort and Median-of-Three Sort shows that the Improved Median-of-Three Sort is more efficient in these scenarios. The results also confirmed that the improved scheme becomes more efficient as the size of the input increases. It was concluded that the Improved Median-of-Three Sort is well suited for some average case sorting scenarios for large value of input size.

Keywords: Sorting, Quicksort, Median-of Three Sort, Improved Median-of-Three Sort, Average Case.