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

[Evgeny Astigeevich]

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,


GrowableArray::stable_sort(C comparator) {
  insertion_sort(_data, length(), comparator);
}


It has a potential problem with O(n^2).

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

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