Insertion Sort (GFG)

 The task is to complete the insert() function which is used to implement Insertion Sort.

Example 1:

Input: N = 5, arr[] = { 4, 1, 3, 9, 7}
Output: 1 3 4 7 9

Example 2:

Input: N = 10, 
arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Output: 1 2 3 4 5 6 7 8 9 10

Your Task: Since this is a functional problem you don't have to worry about input, you just have to complete the function insert(). The printing is done automatically by the driver code.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 1000
1 <= arr[i] <= 1000

SOLUTION:

#Sort the array using insertion sort

def insert(arr):

    #add code here

    for i in range(1,len(arr)):

        key =arr[i]

        j=i-1

        while j>=0 and key<arr[j]:

            arr[j+1]=arr[j]

            j-=1

        arr[j+1]=key