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

[Quan Anh Mai]

On Thu, 19 Jun 2025 22:31:09 GMT, Evgeny Astigeevich <eastigeevich at openjdk.org> wrote:

>> @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.
>
> @merykitty,
> Out of curiosity, why not to use the classical implementations provided above? It's so simple and compact. It's also self documenting. It also has the minimum number of branches.

@eastig It is almost the same, isn't it?

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

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