Parallelization of Cycle Sort Algorithm

Cycle Sort is a straightforward in-place sorting algorithm that is appropriate for certain use cases where limitations on memory or write costs are the main concern. It does this by minimizing the amount of writes to memory. Cycle Sort has an O(n2) time complexity where n is the number of elements in the array to be sorted in both the worst and average cases. Inefficiency may result from this quadratic complexity, particularly for large datasets. This issue can be overcome by applying parallelization techniques to execute this cycle sort algorithm. In this paper, the parallelized solutions for cycle sort using the Message Passing Interface (MPI) programming and Compute Unified Device Architecture (CUDA) programming models are discussed. The elements are separated into smaller arrays, which are then subjected to the sorting cycles in the proposed methods. Until all of the elements in an array are sorted, cycles are applied to them. The findings emphasize the potential advantages of parallelization in reducing the overall computation time for cycle sorting. The outcome of this shows how scalable the parallelized cycle sort method for sorting huge datasets.