Insertion Sort Challenge

You are given a list of integers and your task is to sort the list in ascending order using the Insertion Sort algorithm. Insertion Sort works by building the final sorted array one element at a time. For each iteration, it takes one element, finds the position it belongs within the already sorted part of the array, and inserts it there.

The time complexity of Insertion Sort in the worst case is \(\mathcal{O}(n^2)\), where \(n\) is the number of elements in the list. Although not suitable for very large datasets, this algorithm works efficiently for small or mostly sorted arrays.

inputFormat

The first line contains an integer \(n\) which denotes the number of elements in the list. The second line contains \(n\) space-separated integers.

outputFormat

Output the sorted list in ascending order as space-separated integers.

5
29 10 14 37 13

10 13 14 29 37