A sorting algorithm that builds the final sorted array one at a time. When people sort playing cards, most use a method similar to insertion sort.
Best Case: Ω(n)
Average Case: θ(n²)
Worst Case: O(n²)
where n represents the size of the array.
Worst Case: O(1)
The function insertion_sort has the following parameter(s):
a: the vector of integers to be sorted
Return value: None.
It sorts the vector inplace in ascending order. The original vector gets modified as it is passed by reference.
The first line contains an integer n, the size of array.
The next line contains n space-separated integers a[i] where 0 ≤ i < n.
The array a in sorted order.
5
5 3 1 2 4
1 2 3 4 5