A study of pivot positioning methods for quicksort algorithm

Abstract

Traditionally deterministic algorithm for quicksort is used which gives O (n log n) running time for an average case and O (n2) for the worst case, where n is the number of elements to be sorted. If a randomized approach is used the worst-case running time is reduced to O (n log n). The median of three approaches for choosing pivot and multi-pivot approach like dual pivot also improves the running time. In this paper, we analyze the effectiveness of various pivot positioning methods. To achieve this, we take randomized generated and shorted array of different sizes which provide us with enough data to conclude.