Abstract

The need for parallel sorting algorithms have been driven by the increasing need for large-scale datasets to be processed efficiently. Pigeonhole sorting is one of the sorting algorithms that carries sorting in linear time. This study focuses on enhancing the efficacy of the Pigeonhole Sorting method to improve the performance of the algorithm by employing parallel programming techniques specifically Message Passing Interface (MPI) and Compute Unified Device Architecture (CUDA). The primary objective is to develop and assess parallel solutions for Pigeonhole Sorting, with the aim of optimizing sorting efficiency in data-intensive applications. Commencing with a comprehensive analysis of the sequential design of the Pigeonhole Sorting algorithm, this work proceeds to create parallel implementations using CUDA for Graphics Processing Unit (GPU) acceleration and MPI for distributed memory parallelism. This work contributes valuable insights into adapting the Pigeonhole Sorting algorithm to parallel contexts. The findings emphasize the potential advantages of parallelization in reducing the overall computation time.