The Middle Pivot Element Algorithm

This paper is an improvement over the previous work on New Sorting Algorithm first proposed by Sundararajan and Chakraborty (2007). Here we have taken the pivot element as the middle element of the array. We call this improved version Middle Pivot Element Algorithm (MPA) and it is found that MPA is much faster than the two algorithms RPA (Random Pivot element Algorithm) and FPA (First Pivot element Algorithm) in which the pivot element was selected either randomly or as the first element, respectively. 1. Introduction One of the computational problems that an algorithm encounters is due to the multiple input parameters that has a direct effect on the execution time of the algorithm and we call this problem as one of parameterized complexity of the algorithm. In the recent past much of the work has been done to simulate the parameterized complexity of an algorithm under different situations. The present work is an improvement on the previous works by Sundararajan and Chakraborty [1] in which the New Sorting Algorithm was introduced. In order to make this paper self-contained, we are providing it again. Step 1. Initialize the first element of the array as a pivot element. Step 2. Starting from the second element, compare it to the pivot element. Substep 1. If pivot < element then place the element in the last unfilled position of the temporary array (of same size as the original one). Substep 2. If pivot ≥ element then place the element in the first unfilled position of the temporary array. Step 3. Repeat Step 2 till the last element of the array. Step 4. Finally place the pivot element in the blank position of the temporary array. (Remark: the blank position is created because one element of the original array was taken out as pivot). Step 5. Split the array into two, based on the pivot element’s position. Step 6. Repeat Steps 1–5 till the array is sorted completely. Prashant et al. [2], Anchala and Chakraborty [3, 4], and a recent unpublished paper by the present authors entitled “Parameterized Complexity: A Statistical Approach Combining Factorial Experiments with Principal Component Analysis.” are some of the related works. This last paper compares the parameterized complexity of two algorithms called the RPA (Random Pivot element Algorithm) and FPA (First Pivot element algorithm) in respect to the new sorting technique developed by Sundararajan and Chakraborty [1]. In this paper we have taken the pivot element as the middle term of the array in new sorting technique and call this algorithm MPA (Middle Pivot element algorithm). Thus Step 1 in MPA