Research Article Open Access

A Heapify Based Parallel Sorting Algorithm

M. A.A.A. Hija, A. Zabian, S. Qawasmeh and O. H.A.A. Haija

Abstract

Quick sort is a sorting algorithm whose worst case running time is θ(n2) on an input array of n numbers. It is the best practical for sorting because it has the advantage of sorting in place. Problem statement: Behavior of quick sort is complex, we proposed in-place 2m threads parallel heap sort algorithm which had advantage in sorting in place and had better performance than classical sequential quick sort in running time. Approach: The algorithm consisted of several stages, in first stage; it splits input data into two partitions, next stages it did the same partitioning for prior stage which had been spitted until 2 m partitions was reached equal to the number of available processors, finally it used heap sort to sort respectively ordered of non internally sorted partitions in parallel. Results: Results showed the speed of algorithm about double speed of classical Quick sort for a large input size. The number of comparisons needed was reduced significantly. Conclusion: In this study we had been proposed a sorting algorithm that uses less number of comparisons with respect to original quick sort that in turn requires less running time to sort the same input data.

Journal of Computer Science
Volume 4 No. 11, 2008, 897-902

DOI: https://doi.org/10.3844/jcssp.2008.897.902

Submitted On: 10 September 2008 Published On: 30 November 2008

How to Cite: Hija, M. A., Zabian, A., Qawasmeh, S. & Haija, O. H. (2008). A Heapify Based Parallel Sorting Algorithm. Journal of Computer Science, 4(11), 897-902. https://doi.org/10.3844/jcssp.2008.897.902

  • 2,669 Views
  • 3,952 Downloads
  • 2 Citations

Download

Keywords

  • Parallel sorting
  • heap sort
  • Quick sort
  • in-place sorting