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

[Cesar Soares Lucas]

On Thu, 19 Jun 2025 17:15:22 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

>> Hi,
>> 
>> This PR adds an implementation of insertion sort to Hotspot. It is an algorithm that is inplace and stable, and it is the ideal algorithm for arrays with small numbers of elements. The motivation for this is [JDK-8357186](https://bugs.openjdk.org/browse/JDK-8357186) in which a stable sort is desired and the number of elements is small. Additionally, since insertion sort is the most efficient sorting algorithm for small arrays, it can be used in non-stable sort as well.
>> 
>> In addition, I make some improvements to `GrowableArrayIterator`:
>> 
>> - Make a non-const variant (our current iterator is const only).
>> - Add various utility operators to align with a typical iterator.
>> 
>> [JDK-8360032](https://bugs.openjdk.org/browse/JDK-8360032) is a follow-up work that will build a stable merge-insertion sort on top of this PR.
>> 
>> Please take a look and share your thoughts. Thanks very much.
>
> Quan Anh Mai has updated the pull request incrementally with one additional commit since the last revision:
> 
>   give up on RandomIt

Just some drive-by comments.

src/hotspot/share/utilities/sort.hpp line 37:

> 35: public:
> 36:   template <class T, class Compare>
> 37:   static void sort(T* data, int size, Compare comp) {

`int size` to `size_t size` ? or at least `unsigned int`.

src/hotspot/share/utilities/sort.hpp line 39:

> 37:   static void sort(T* data, int size, Compare comp) {
> 38:     if (size == 0) {
> 39:       // Empty array

NIT: useless comment.

src/hotspot/share/utilities/sort.hpp line 57:

> 55:         // backward)
> 56:         T* prev = pos - 1;
> 57:         if (comp(*prev, current_elem) <= 0) {

NIT: would be better to pass pointers here?

test/hotspot/gtest/utilities/test_sort.cpp line 25:

> 23:  */
> 24: 
> 25: #include "runtime/os.hpp"

NIT: sort the imports?

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

PR Review: https://git.openjdk.org/jdk/pull/25895#pullrequestreview-2943777844
PR Review Comment: https://git.openjdk.org/jdk/pull/25895#discussion_r2157486802
PR Review Comment: https://git.openjdk.org/jdk/pull/25895#discussion_r2157487754
PR Review Comment: https://git.openjdk.org/jdk/pull/25895#discussion_r2157490818
PR Review Comment: https://git.openjdk.org/jdk/pull/25895#discussion_r2157491825