Comparison Time Execution and Memory Usage of Dual-Pivot Quick Sort and Parallel Merge Sort

EasyChair Preprint 10570

Abstract

Various algorithms have been used to sort data. now it has very algorithms that have been optimized to be more efficient. We used the algorithms from quicksort and mergesort but modified versions, namely dual-pivot quicksort and parallel mergesort. In this research, we use a case study method to compare the performance of dual-pivot quicksort and parallel mergesort algorithms. We use Java programming language to implement both algorithms. Using a dataset of 10000 book ID data with the integer data type, we will compare the two algorithms in terms of execution time and memory usage. The comparison results show that dual-pivot quicksort is faster than parallel mergesort and also uses less memory than parallel mergesort. This shows that the algorithm of the advanced version of quicksort, namely dual-pivot quicksort, is better than the advanced version of mergesort, namely parallel mergesort. We also identified that dual-pivot on quicksort has significantly more impact than parallel mergesort. It can happen because parallel mergesort only speeds up the queue on recursive which while it helps but is not very significant. This research helps in choosing the best algorithm for sorting in terms of execution time and memory used so that in the future each algorithm is used according to its capacity so that each algorithm can work as efficiently as possible.

Keyphrases: Memory Usage, Parallel Mergesort, dual pivot quicksort, execution time

@booklet{EasyChair:10570,
  author    = {Kevin Chayadi and Edward Lauwis and Vicky Frandy Lius and Kristien Margi Suryaningrum and Hanis Amalia Saputri},
  title     = {Comparison Time Execution and Memory Usage of Dual-Pivot Quick Sort and Parallel Merge Sort},
  howpublished = {EasyChair Preprint 10570},
  year      = {EasyChair, 2023}}