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

[Quan Anh Mai]

On Thu, 19 Jun 2025 14:27:06 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.
>> 
>> 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:
> 
>   GrowableArrayNonConstIterator

Firstly, since the generalized function is no more complex than the specialized function, so why not go for the generalized function and save us the troubles generalizing the specialized function if the need arises.

Secondly, it is much much easier to test the generalized function. I can easily verify that sorting an array of `int` is correct but I cannot verify that the sort of an array of `SigEntry`s is correct, especially when I am also modifying the compare function. Additionally, a stable sort is needed because it is non-trivial to obtain the desired effect with a non-stable sort. At the same time, I can easily make a `TwoInt` that is compared by `val` and `idx` stores the index in the original array.

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

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