DualPivotQuicksort in Java

Sorting Algorithms

4 min read1 day ago

The interface of DualPivotQuicksort

/**
 * Sorts the specified array using the Dual-Pivot Quicksort and/or
 * other sorts in special-cases, possibly with parallel partitions.
 *
 * @param sorter parallel context
 * @param a the array to be sorted
 * @param bits the combination of recursion depth and bit flag, where
 *        the right bit "0" indicates that array is the leftmost part
 * @param low the index of the first element, inclusive, to be sorted
 * @param high the index of the last element, exclusive, to be sorted
 */
static void sort(Sorter sorter, int[] a, int bits, int low, int high)

bits we often use a combination of recursion depth and bit flags to keep track of our progress.

Here, “bits” refers to the binary representation of a number. Each bit in this number can serve a different purpose:

Recursion Depth: Some of the bits are used to store the depth of recursion. This is useful in recursive algorithms to know how “deep” you’ve gone into the recursion.
Bit Flag: Other bits are used as flags, which are boolean indicators used to represent a specific condition. The condition can be anything that’s relevant to your algorithm.

In this specific case, the rightmost bit (also known as the least significant bit) is used as a flag to indicate whether an array is the leftmost part. If the right bit is 0, it means the array is the leftmost part. If it were 1, it would mean the array is not the leftmost part.

This kind of encoding is a very efficient way to store multiple pieces of information in a single number and is commonly used in low-level programming and algorithms. However, it can make the code harder to understand and debug, so it’s important to document what each bit represents, just like in the comment in the code.

Comparing the Time Complexity

https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course

Insertion Sort

/**
 * Max array size to use mixed insertion sort.
 */
private static final int MAX_MIXED_INSERTION_SORT_SIZE = 65;

/*
 * Run mixed insertion sort on small non-leftmost parts.
 */
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
    sort(int.class, a, Unsafe.ARRAY_INT_BASE_OFFSET, low, high, DualPivotQuicksort::mixedInsertionSort);
    return;
}

/**
 * Max array size to use insertion sort.
 */
private static final int MAX_INSERTION_SORT_SIZE = 44;

/*
 * Invoke insertion sort on small leftmost part.
 */
if (size < MAX_INSERTION_SORT_SIZE) {
    sort(int.class, a, Unsafe.ARRAY_INT_BASE_OFFSET, low, high, DualPivotQuicksort::insertionSort);
    return;
}

Insertion sort takes O(n²) time in the worst case. Because its inner loops are tight, however, it is a fast sorting algorithm for small input sizes.

Moreover, unlike merge sort, it sorts in place, meaning that at most a constant number of elements of the input array are ever stored outside the array, which can be advantageous for space efficiency.

Heap sort

/**
 * Max recursive partitioning depth before using heap sort.
 */
private static final int MAX_RECURSION_DEPTH = 64 * DELTA;

/*
 * Switch to heap sort if execution
 * time is becoming quadratic.
 */
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
    heapSort(a, low, high);
    return;
}

Heapsort sorts n numbers in place in O(n lg n) time.

Heapsort is an efficient sorting algorithm that works well for large data sets, so it’s used here as a fallback when the recursion depth gets too high.

Quicksort

Quicksort sorts n numbers in place, but its worst-case running time is O(n²). Its expected running time is O(n lg n), however, and it generally outperforms heapsort in practice.

Like insertion sort, quicksort has tight code, and so the hidden constant factor in its running time is small. It is a popular algorithm for sorting large arrays.

The reason for this switch is that quicksort has a worst-case time complexity of O(n²) when the recursion depth becomes too high, while heap sort has a worst-case time complexity of O(n log n). So, switching to heap sort when the recursion depth gets too high can prevent the execution time from becoming O(n²).