A three dimensional bubble sort algorithm?

Question

Recently I’ve learned two basic sorting algorithms bubble and heap sort. It’s fairly clear that heap sort is a “2D” version of the “1D” bubble sort. For both algorithms, you find the largest element in each round, but for heap sort you leverage transitivity of comparison to find the max quicker. My naive question is the following: can you make a data structure where you implement a “3D” version of bubble sort to get an even faster speedup than nlogn? If not, what’s the constraint - is there something fundamental “2D” to sorting?

Most material I’ve found on this site are questions asking to sort a 3D array. That’s not my question. I’m asking if we’re can assign a 3D data structure to a 1D array, or if there’s a fundamental obstruction.

Answer 1

Here are some aspects to analyse the comparison between bubble sort and heapsort:

Aspect	Bubble sort	Heapsort
preprocessing	none	Floyd's maxheap construction algorithm, starting half-way sifting values to the right, and gradually adding more values from the left.
sorted partition	located at the right, growing with each iteration	located at the right, growing with each iteration
unsorted partition	at the left: no invariant	at the left: it is a maxheap (no child is greater than its parent)
location of greatest value in unsorted partition	anywhere	at index 0
grow sorted partition	nothing to do after bubble iteration completed	swap first value (root of heap) with last
bubbling	bubble any value to the right that is greater than its right neighbor ("child") following the linear path, leaving the greatest value of the unsorted partition at the right side of it	bubble a single value to the right when it is less than its child, following the tree path, where the first potential swap guarantees that the root (at index 0) has the max value of the unsorted partition.
stop bubbling	when reaching the end of the unsorted partition	when no more swap occurs.

Although there are some similarities (there is some concept of "bubbling", and the sorted partition grows at the right), many aspects are different and have no clear correspondence.

Moreover, there is no clear mapping to "dimensions" as if bubble sort is 1D and heapsort is 2D. If the "2" in 2D is a reference to the binary tree, then mapping that back to the 1D world would lead to the following observation: we would have a "tree" with degree 1, where each node has one child (except the only leaf), which sits at the next index. Turning that into a list that obeys the "heap property" (for 1D), really means sorting the array. So then the preprocessing step would sort the array in descending order, and that would look more like a right-to-left insertion sort, not bubble sort.

Extending to 3D?

If the 2D aspect refers to the binary tree, then surely we can make -ary heaps, sorting the array with the same principle of deleting the root of the heap and adding it to the sorted partition. However, there is no asymptotically significant performance gain to be expected. Wikipedia mentions there is a benefit for "decrease priority operations", but that operation plays no role in heapsort.

Moreover, it is known that the number of comparisons required to sort a list with a comparison-based sorting algorithm is in the worst case O(log), so heapsort (with binary heap) already achieves that optimum.