# A Hybrid Hoare-Lomuto Partition Scheme and Bubble Sort for Small Arrays

DevFeed: [A Hybrid Hoare-Lomuto Partition Scheme and Bubble Sort for Small Arrays](<https://devfeed.tech/articles/hoare-s-rebuttal-and-bubble-sort-s-comeback-21134.md>)

Original publisher: [Read original article](<https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html>)

Author: Gerben Stavenga

Published: 2020-05-29T00:00:00Z

Content type: article

Language: en

Sources: [Josh Haberman](<https://devfeed.tech/sources/josh-haberman.md>)

Topics: [Sorting](<https://devfeed.tech/topics/sorting.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Programming](<https://devfeed.tech/topics/programming.md>)

Tags: [parallelism](<https://devfeed.tech/tags/parallelism.md>), [partition](<https://devfeed.tech/tags/partition.md>), [partitioning](<https://devfeed.tech/tags/partitioning.md>), [performance](<https://devfeed.tech/tags/performance.md>), [sorting](<https://devfeed.tech/tags/sorting.md>)

## AI overview

This article examines QuickSort performance, focusing on branch mispredicts, branchless Lomuto partitioning, and a hybrid Hoare-Lomuto scheme. It reports that Bubble Sort performs best for small arrays in the discussed experiments, attributing the gains to instruction-level parallelism and shorter dependency chains.

## Source excerpt

Editor's note: For this blog entry I welcome my friend and colleague Gerben Stavenga as a guest author. Recently Andrei Alexandrescu published an interesting post about optimizing QuickSort using the Lomuto partition scheme. The essence of that post is that for many situations the performance of QuickSort is completely dominated by branch mispredicts and that a big speed up can be achieved by writing branchless code. This has been observed by many, and various branchless sorting routines have been proposed. Andrei observed that from the two well known QuickSort partitioning schemes Lomuto is easily implemented branchless, and this indeed performs much better for sorting small primitives. I recently experimented with similar ideas but took them in a different but interesting direction. I discovered that a hybrid of the Hoare and Lomuto schemes can deliver a large improvement even compared with branchless Lomuto. And the final surprise is that Bubble Sort takes the crown for small arrays. The key to all these wins is exploiting instruction-level parallelism and reducing dependency chains. Basic QuickSort fundamentals Quicksort refers to a class of algorithms for sorting an array that all share the same outline void QuickSort(T* left, T* right) { if (right - left > kCutOff) { auto pivot = ChoosePivotElement(left, right); // Important but not focus here auto p = Partition(pivot, left, right); // The main work loop QuickSort(left, p); QuickSort(p, right); // Tail call, ideally the largest sub-interval } else { SortSmallArray(left, right); } } Countless variations exist varying in the choice of kCutOff, choice of the sorting algorithm for the small arrays and choice of pivot element. These are important for performance but the main work QuickSort performs is done in the Partition function. There are two canonical schemes for implementing Partition: the original Hoare scheme and the Lomuto scheme. The Hoare partition scheme works by swapping elements that violate the parti