A brief introduction to a new stable sorting algorithm - Quadsort

1. Overview

We’ll discuss Quadsort in this article. It’s a new stable sorting algorithm. We’ll begin from the concept of stable sorting and some sorting algorithms. Then, we’ll discuss the Quadsort algorithm step by step. We’ll discuss an example of Quadsort with flowchart to show in the process.

2. Stable Sorting Algorithms

The relative order of the identical elements before and after sorting are the same in the stable sorting algorithms. In other words, these keep the relative order of elements. Stability is important in areas like data processing, where we need to keep original sequence of the identical elements. So we can handle multiple keys. There are different stable sorting algorithms like merge sort and tim sort. These two algorithms have time complexities of O(n logn) for n values. Similarly, Quadsort also has the same time complexity, i.e., O(n logn). We use quadsort in datasets that are partially sorted.

3. Quadsort Algorithm

3.1 General Idea

Quadsort ia a bottom, adaptive and branchless mergesort. We divide the input array into segments of eight elements each. We sort each block and then merge them until the entire array is sorted. The algorithm is given as below –

Divide: We divide the array into blocks of eight elements.
Analyze and Sort: We analyze each block to check order of elements for in order, reverse order and random order. We skip already sorted blocks and reverse the order of reverse order blocks to make them in order. We sort random order blocks using branchless swaps then parity merge to sort them.
Merge: After sorting all blocks. We merge these back together until the full array is sorted.

So we divide the array into smaller blocks. Quadsort sorts randomly order blocks. Then merges all sorted blocks to make full array sorted. This algorithm is stable throughout the process.

3.2 Analyzing and Sorting Each Block

Quadsort uses Quad Swap Analyzer to check order of each block. Quad Swap Analyzer tells you order of each block whether block is in order, reverse order and random order.

Ordered Block: We skip already sorted orders.
Reverse-Ordered Block: We reverse the order of each reverse ordered block.
Random Block: We use branchless swaps and parity merge to sort each random order block.

4. Example

Cosider this block of eight elements of the input array is –

A = [9, 3, 7, 1, 12, 5, 8, 2]

Step 1: Divide

We divide given input array into blocks of eight elements. Since our given input array is already block of eight elements, so we’ll move to next step to work on this block according to quardsort algorithm.

Step 2: Analyze and Sort with the Quad Swap Analyzer

We’ll find order of given block using quad swap analyzer –

Compare (9, 3): Reverse-ordered
Compare (7, 1): Reverse-ordered
Compare (12, 5): Reverse-ordered
Compare (8, 2): Reverse-ordered

Since we’re comparing 4 pairs each time, i.e., quadruple, so this is why we called this sorting algorithm as Quadsort.

Here, according to algorithm bitmask value will be 15. It means all pairs are reverse ordered. We can also compare remaining pairs (i.e., (3, 7), (1, 12), (5, 8)) to confirm block is not sorted completely.

Since bitmask is 15 so we’ll reverse this block according to rule –

= [2, 8, 5, 12, 1, 7, 3, 9]

Then we’ll use parity merge to make this block fully sorted –

= [1, 2, 3, 5, 7, 8, 9, 12]

Similarly, we’ll work on each block to sort them separately.

Step 3: Merge

We’ll merge each sorted block iteratively. We use ping-pong merge technique instead of normal merge technique to merge sorted blocks. Ping-Pong merge technique merges 4 blocks instead of 2 block at a time. Like below –

In our example there is only one block so no need to merge it with anyone because no other block is available.

We sort each block individually before merging in the above steps. So this algorithm preserves order of duplicate elements, i.e., stability.

5. Flowchart of Quadsort

This is flowchart of Quadsort. As shown below, it illustrates the main steps in the process –

We divide the array into blocks of eight elements. Then sort each of these, merge them until full the array is sorted.

6. Pseudocode for Quadsort

Next, here is the pseudocode for the step of this algorithm.

6.1 Main algorithm

algorithm Quadsort(array):
    // INPUT
    //    array = the unsorted collection
    // OUTPUT
    //    the sorted collection

    blockSize <- 8

    // Step 1: Divide array into blocks and analyze and sort each block
    for start <- 0 to array.length by blockSize:
        end <- min(array.length - 1, start + blockSize - 1)
        analyzeAndSortBlock(array, start, end)

    // Step 2: Iteratively merge sorted blocks
    mergeSize <- blockSize
    while mergeSize < array.length:
        for left <- 0 to array.length by mergeSize * 2:
            mid <- left + mergeSize - 1
            right <- min(array.length - 1, left + (2 * mergeSize) - 1)
            if mid < right:
                pingPongMerge(array, left, mid, right)
        mergeSize <- mergeSize * 2

6.2 Analyze and sort each block algorithm

algorithm analyzeAndSortBlock(array, start, end):
    // INPUT
    //    array = input collection
    //    start = start index
    //    end = end index
    // OUTPUT
    //    the block is sorted

    bitmask <- createBitmaskForComparisons(array, start, end)

    if bitmask == 0:
        return // Already ordered
    if bitmask == 15:
        reverseBlock(array, start, end) // Reverse ordered
        return

    performBranchlessSwaps(array, start, end)
    parityMerge(array, start, end)

6.3 Merge sorted blocks using Ping-Pong merge

algorithm pingPongMerge(array, left, mid, right):
    // INPUT
    //    array, left = start of left block
    //    mid = end of left block
    //    right = end of right block
    // OUTPUT
    //    merged sorted collection between left and right

    leftArray <- array[left : mid]
    rightArray <- array[mid + 1 : right]

    leftIndex <- 0
    rightIndex <- 0

    while leftIndex < len(leftArray) and rightIndex < len(rightArray):
        leftValue <- leftArray[leftIndex]
        rightValue <- rightArray[rightIndex]
        
        if leftValue < rightValue:
            array[left + leftIndex + rightIndex] <- leftValue
            leftIndex <- leftIndex + 1
        else:
            array[left + leftIndex + rightIndex] <- rightValue
            rightIndex <- rightIndex + 1

    // Append remaining elements
    for leftIndex <- leftIndex to len(leftArray) - 1:
        array[left + leftIndex + rightIndex] <- leftArray[leftIndex]

    for rightIndex <- rightIndex to len(rightArray) - 1:
        array[left + leftIndex + rightIndex] <- rightArray[rightIndex]

In these pseudocodes –

We divide the array in blocks of eight elements. Analyze the order of each block. We skip in order blocks. We reverse the order of reversed order of blocks. We sort random order blocks ng branchless swaps and parity merge.
Then we merge already sorted blocks using ping-pong merge technique.

7. Complexity Analysis

The time complexity of the Quadsort algorithm is O(n logn). The n is the number of the elements in the array. We just divide, sort and merge blocks. Quadsort preserves the order of duplicate elements, i.e., stability. We can compare quadsort with mergesort and quicksort like in below table –

8. Conclusion

In Summary, we’ve discussed Quadsort algorithm in this article. Overall, it’s new stable sorting algorithm. We discussed stable sorting concepts and an example of Quadsort. We discussed the pseudocode and flowchart. This algorithm gives you efficiency in partially sorted data.