Insertion Sort

Problem

Given an array of integers numbers, sort the array in ascending order using the insertion sort algorithm.

Algorithm

1. Choose a pivot element from the array.
2. Partition the array around the pivot, such that all elements less than the pivot are moved to the left of the pivot, and all elements greater than the pivot are moved to the right of the pivot.
3. Recursively sort the left and right sub-arrays.

Examples:

insertionSort([9,4,7,3,5,8,1,6,2]);
// Output: [1,2,3,4,5,6,7,8,9]

Time Complexity

The worst-case time complexity of Insertion Sort is O(n^2), where n is the number of elements in the array. However, the best-case time complexity is O(n) for an already sorted array.