CFP last date
21 October 2024
Reseach Article

Threshold Analysis and Comparison of Sequential and Parallel Divide and Conquer Sorting Algorithms

by Tinku Singh, Durgesh Kumar Srivastava
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 145 - Number 10
Year of Publication: 2016
Authors: Tinku Singh, Durgesh Kumar Srivastava
10.5120/ijca2016910792

Tinku Singh, Durgesh Kumar Srivastava . Threshold Analysis and Comparison of Sequential and Parallel Divide and Conquer Sorting Algorithms. International Journal of Computer Applications. 145, 10 ( Jul 2016), 28-33. DOI=10.5120/ijca2016910792

@article{ 10.5120/ijca2016910792,
author = { Tinku Singh, Durgesh Kumar Srivastava },
title = { Threshold Analysis and Comparison of Sequential and Parallel Divide and Conquer Sorting Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { Jul 2016 },
volume = { 145 },
number = { 10 },
month = { Jul },
year = { 2016 },
issn = { 0975-8887 },
pages = { 28-33 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume145/number10/25316-2016910792/ },
doi = { 10.5120/ijca2016910792 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:48:27.072704+05:30
%A Tinku Singh
%A Durgesh Kumar Srivastava
%T Threshold Analysis and Comparison of Sequential and Parallel Divide and Conquer Sorting Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 145
%N 10
%P 28-33
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

One of the basic problems in computer science is sorting that need to be fast and efficient, since data is growing day by day. Various applications need fast sorting algorithms like Big Data analyses particularly in large scale scientific, social/web mining and commercial application domains. Divide and conquer Sorting Algorithms (Quick sort and merge sort) provides the best running time among all the sorting algorithms. When parallelism is applied to these algorithms, new performance leaps are accomplished. Recent parallel programming procedures and environment needs profound changes in programs to accomplish parallelism furthermore constitute puzzling, confounding and mistake inclined constructs and standards. When the number of processors utilization gets large, the overhead of thread synchronization and processor scheduling gets increase, this diminishes the speedup. In this paper, two algorithms are designed using C# viz. parallel quick sort and parallel merge sort that uses Parallel.Invoke() method. Both algorithms when executed over multicore architecture compute the threshold beyond which the above mentioned algorithms achieve speedup in comparison to its sequential version, Also threshold is calculated and compared for both the algorithms for uneven input size.

References
  1. Rohit Yadav, Nitin Kr. Verma and Kratika Varshney, Volume 3, Issue 11, November 2013, Analysis of Recursive and Non-recursive Merge Sort Algorithm, International Journal of Advanced Research in Computer Science and Software
  2. Sabahat Saleem, M. IkramUllah Lali1, M. Saqib Nawaz1 and Abou Bakar Nauman, Vol.7, No.2 (2014), pp.151-164, Multi-Core Program Optimization: Parallel Sorting Algorithms in Intel Cilk Plus, International Journal of Hybrid Information Technology
  3. Alaa Ismail El-Nashar, Vol.2, No.3, May 2011 PARALLEL PERFORMANCE OF MPI SORTING ALGORITHMS ON DUAL–CORE PROCESSOR WINDOWS-BASED SYSTEMS, International Journal of Distributed and Parallel Systems (IJDPS)
  4. Ishwari Singh Rajput, Bhawnesh Kumar and Tinku Singh, Volume 57– No.9, November 2012, Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms, International Journal of Computer Applications (0975 – 8887).
  5. Ishwari Singh Rajput, Deepa Gupta, Vol. 2 Issue 3 May 2013, An Adaptive framework for Parallel Merge Sort Algorithm on Multicore Architecture, International Journal of Latest Trends in Engineering and Technology (IJLTET).
  6. G. Koch, 2013 March 5, Multi-Core Introduction”, Intel Developer Zone, https://software.intel.com/en-us/articles/multi-core-introduction.
  7. Archana Ganesh Said, Volume 6, Issue 4, April 2016, Multi-core Processors – A New Approach towards Multiprocessing, International Journal of Advanced Research in Computer Science and Software Engineering.
  8. Abdulrahman Hamed Almutairi & Abdulrahman Helal Alruwaili, Volume 12 Issue 10 Version 1.0, Year 2012, Improving of Quicksort Algorithm Performance by Sequential Thread or Parallel Algorithms, Global Journal of Computer Science and Technology Hardware & Computation.
  9. Nitin Chaturvedi, S Gurunarayanan, Vol.4, No.4, July2013, STUDY OF VARIOUS FACTORS AFFECTING PERFORMANCE OF MULTI-CORE PROCESSORS, International Journal of Distributed and Parallel Systems (IJDPS).
  10. http://people.eecs.berkeley.edu/~yelick/cs194f07/lectures /lect01-whyparallel.pdf
  11. Christian Martin, embedded world 2014, Multicore Processors: Challenges, Opportunities, Emerging Trends, exhibition & conference.
  12. Dali Ismail, http://www.cse.wustl.edu/~jain/cse567-13/ftp/multicore.pdf
Index Terms

Computer Science
Information Sciences

Keywords

Parallel threshold multicore speedup sorting complexity processor.