1. Description
Quadsort can be described as a faster merge sort. Unlike merge sort, which makes comparisons of 2 elements at a go while performing a sorting operation, Quadsort compares 4 elements at a go. It defeats the performance of Merge sort and Quicksort, which have long been considered the best sorting algorithms.
2. Implementation
Quadsort does require a successful implementation of the following methods:
i) Quad-swap -This is the main building block of Quadsort.
ii) Merging (This is where a sorted block of 4 elements is merged with another block of 4 elements or, generally, two sorted arrays are merged into one)
iii) Performing a check to see if the block of 4 elements is sorted already, either in-order, or in reverse order.
The whole array is segmented into chunks of 4 elements, and each chunk is sorted using the Quad-swap approach, then all chunks are merged together in sorted order.
Quad-swap compares and sorts 4 array elements at a go, as can be seen in the Pseudocode below:
With the simple Quadswap above, if an array is already fully sorted it writes a lot of data back and forth from swap unnecessarily. If an array is fully in reverse order, the algorithm will change numbers 10, 9, 8, 7, 6, 5, 4 to 7, 8, 9, 10, 6, 5, 4
This will reduce the degree of orderliness rather than increase it. This problem can be solved by implementing 'Quad-swap in-place', which involves checking and handling the reverse order. Reverse order may be handled using a simple reversal function, as can be seen below:
After sorting, the blocks need to be merged. If this is done by merging 4 blocks at once, this is known as Quad-merge or Ping-pong merge.
Our merging approach makes use of Timsort’s galloping merge algorithm to merge two arrays. We create an empty array, that is continuously merged with every new chunk of sorted 4 elements.
As seen while performing Quad-swap above, it is ideal checking whether the four blocks are in order. If they are in order, the merge operation is skipped. While performing the in-place Quadswap, we have already checked the reverse order. Thus, there is no need for rechecking it while performing the merge operation.
3. Other Merge Operations
3.1. Parity Merge
Parity merge works that, given 2 n length arrays, we can be able to perform n merge operations at the start of each array, and n merger operations at the end of each array. One needs to ensure that the two arrays are of equal length.
3.2. Hybrid Parity Merge
In the case the two arrays are not of equal length, we then need to perform a hybrid parity merge. A hybrid parity merge works by taking n parity merges, where n is the length of the smaller array. Once this is completed, it will then switch to the traditional merge.
Parity merge is very necessary for branchless optimisations, and this is because it helps in speeding up the sorting of random data. Another advantage of parity merge is that two separate memory regions can be accessed in the same loop, and this allows for memory-level parallelism. On most hardware, this increases the runtime speed by 2.5 times for random data.
3.3. Branchless Parity Merge
Branchless parity merge works well for random data. However, it slower sorting ordered data. This is where the Quad galloping merge comes in. Quad galloping merge makes use of the galloping idea introduced by Timsort.
The galloping merge algorithm may be implemented as follows:
When merging ABC and XYZ, for instance, it first checks if B is smaller or equal to X. If so, A and B are copied to swap. If not, it checks if A is greater than Y. If so, X and Y are copied to swap.
If either of the checks is false, it is known that the two remaining distributions are A X and X A. This will allow the execution of an optimal branchless merge.
Overally, the Quad galloping merge performs better for both ordered and unordered data.
Other merge operations you may also want to look at are the Tail-merger and the Rotate-merge.
Let’s take a look at a complete python implementation of the Quadsort algorithm. This will include calling the sorting and merging algorithms already implemented above, and may appear as follows:
4. Complexity analysis
4.1. Time Complexity
4.2. Space Complexity
5. Conclusion
Quadsort performs better than Merge sort, and Quick sort in most runtime tests, except for generic data. Unlike Quick sort, it is able to pick a reliable pivot, hence the better performance for small arrays. For arrays exceeding the L1 cache, Quicksort performs better due to its ability to partition.
Top comments (0)