Advanced Quick Sort with Parallel Processing

Abstract: Quick sort algorithm is a sorting algorithm that works on the principle of divide-and-conquer, making sub- lists(sub-array) out of the given problem domain and then recursively applying the same swapping technique till the whole list is sorted. There are numerous operations involving comparison, swapping and assignments in the quick sort algorithm. In this paper we have proposed a new algorithm that is an enhanced version of original quick sort. The idea behind this is to reduce the number of steps, in order to achieve that we have introduced parallel processing which simultaneously deals with number of sub-arrays at the same time. The algorithm is recursive, but with the help of parallel processing the number of steps is considerably reduced and all the cases can be easily dealt with. There is more requirement of memory in this algorithm since all the sub-arrays are parallel processed, but there is significant reduction in time complexity when the list contains large number of elements.

Keywords: Slots, parallel processing, touched elements, reference element, MIN and MAX.