RFR: 8360023: Add an insertion sort implementation to Hotspot [v3]

[Johan Sjölen]

On Thu, 19 Jun 2025 16:31:52 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Note that insertion sort is the most efficient sorting algorithm for small arrays, so we can use it for non-stable sort as well.
>
> Hi @merykitty ,
> 
> Thank you for taking the effort to produce tooling for everyone when you found a need for it yourself. Often, we have useful datatypes hidden away into internals that we'd like to use, or we simply do other solutions because our preferred solution is missing.
> 
> Unfortunately, I think that the ceremony required to get your insertion sort working for someone else's type will put other devs off from using it. None, AFAIK, of our datatypes are compatible with the STL's interfaces.
> 
> If we take this definition:
> 
> 
> void GrowableArrayView<>::insertion_sort(int f(E*, E*)) {
>     if (_data == nullptr) return;
>     for (int i = 1; i < length(); i++) {
>         E key = _data[i];
>         int j = i - 1;
>         while (j >= 0 && f(_data[j], key)) {
>             _data[j + 1] = _data[j];
>             j--;
>         }
>         _data[j + 1] = key;
>     }
> }
> 
> 
> And change it around a bit:
> 
> 
> template<typename T, typename C>
> void insertion_sort(T* array, size_t length, C comparator) {
>     for (int i = 1; i < length; i++) {
>         T key = array[i]; // Should it really copy???
>         int j = i - 1;
>         while (j >= 0 && comparator(array[j], key)) {
>             array[j + 1] = array[j];
>             j--;
>         }
>         array[j + 1] = key;
>     }
> }
> 
> 
> Then I think we have something general-ish.
> For stable_sort we then do:
> 
> 
> GrowableArray::stable_sort(C comparator) {
>   insertion_sort(_data, length(), comparator);
> }
> 
> 
> This is going to be general enough, for most of our cases we have a contiguous array with a size of some fixed element type which we want to change in-place. This is sufficient for expressing that.
> 
> This also fits well with the `QuickSort` class that we have, it's the same type of interface. Maybe the `quickSort.hpp` should be renamed into `sort.hpp` and `InsertionSort` be a class in there? I'm not sure what the style guide thinks about that, but I think it's a good idea :-).

> @jdksjolen Thanks for your suggestion. Actually, I can make it so that a `T*` will satisfy `RandomIt` but there is no need for `RandomIt` right now. It is unfortunate because an iterator will give us more safety net, though.
> 
> I have reverted the `GrowableArrayIterator` changes. Insertion sort is good for small arrays so we can use it for `QuickSort::sort`, too. For a stable sort algorithm, implementing a merge - insertion sort should be the way, there is no need to rush for a stable sort method.

Cheers! This looks good to me. Let's see what the rest of the community thinks.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/25895#issuecomment-2988777575