Insertion Sort
Generate Random Values
Enter the number of random values to generate
Input Your Own Values
Enter a list of numbers separated by a comma
Whats goin on?
Insertion sort is an algorithm that steps through an array and places elements relative to the elements it has already passed. In other words, every element behind the current one can be considered sorted. Therefore, the if the current element is smaller than the previous element, swap the two and repeat until the element is in the correct position. If the current element is larger, increment the current element to the next position. Repeat until all of the items are sorted.
Performance
Time complexity
Because each iteration has an additional iteration through the array backwards, the time complexity of insertion sort is
O(n^2)
Space complexity
Insertion sort only needs one additional space in memory to perform the swap so its space complexity is
O(1)