Parallel Implementation of Dutch Flag Sorting Algorithm Using MPI and CUDA

This paper focuses on improving the performance of the Dutch flag sorting algorithm for large datasets with many duplicates using parallel computing techniques. Traditional quicksort struggles with many comparisons and swaps, especially with repeated elements. By partitioning the data into three sections—values less than, equal to, and greater than a pivot—the three-way quicksort eliminates unnecessary steps, enhancing efficiency. The study explores parallel versions of Dutch flag sort using Compute Unified Device Architecture (CUDA) for GPU acceleration and Message Passing Interface (MPI) for distributed systems, comparing their speed and scalability. The parallel implementations leverage the computational power of modern architectures to handle large-scale datasets with exceptional speed and efficiency. The findings include comparative performance metrics, such as sorting 1,500,000 elements in 74.4 ms sequentially, 3.089 ms with MPI, and 0.530 ms using CUDA. The proposed parallel implementations are expected to significantly improve sorting speed, particularly for datasets with frequent duplicates, making them ideal for applications in database systems and large-scale data analysis. The findings suggest that parallel three-way quicksort could be a reliable option for high-performance computing environments, improving sorting efficiency across various domains.