Fix Sort: A Good Strategy to Perform Segmented Sorting

摘要

In order to solve many real problems, we have to sort array segments of data. This sorting task is called segmented sorting. Problems like image processing and suffix array construction usually have huge amount of data and their solutions make use the segmented sorting procedure. There are several techniques for solving the segmented sorting. A previous work showed that a strategy called fix sort had a good performance to sort segments of arrays. This strategy adjusts the input array to allow off-the-shelf general sorting algorithms to execute segmented sorting. Besides the extensive tests that were done in the previous work, the implemented fix sort solution did not explore in full the proposed parallel algorithm. In this work we revisit the sequential and parallel algorithms to the fix sort strategy creating new parallel and sequential implementations. We compared our results with the previous methods to sort multiple segments. The obtained results showed that our implementations of fix sort strategy achieved better execution times than the previous ones.