Hands-On Data Structures and Algorithms with JavaScript

What is Insertionsort

Insertionsort, as the name suggests, is a type of sort in which we extract elements from the input dataset one by one and then insert them in the sorted result dataset after determining where the element should be placed.

We can straight away determine that this approach will require an extra set (of the same size as the input) to hold the results. So, if we have a Set of 10 elements as the input, we will need another Set for the output whose size would be 10 as well. We can switch around this approach a little bit so that our sorting happens in-memory. Performing an action in-memory means that we will not request for any more memory (by creating extra sets of the same size as the input).