Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version. Efficient for (quite) small data sets, much like other quadratic sorting algorithms More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position Stable; i.e., does not change the relative order of elements with equal keys.

Clicking on this step you can see the Video learningstep of the algorithm.

Video

As a first step you will be able to watch the video representation of the Bubble sort algorithm. This will be presented by hungarian folk dance.


Pay attention and try to understand the main movements of the sorting algorithm, namely the comparison, selection and swap.


This technique involves human movement effect in order to visualize the algorithm in a dinamic way. Enjoy it! :)