Insertion Sort using Python

Insertion sort is a simple sorting algorithm that works by iterating through the list and inserting each element in its correct position in the sorted list. It is an in-place sorting algorithm, which means it doesn't require any additional space to sort the list.

def insertion_sort(arr):
    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

# Test the function
arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print(arr)  # Output: [1, 2, 3, 4, 5, 6]

To sort the list, the algorithm iterates through the list and compares each element with the elements that come before it. If an element is smaller than the element before it, it is inserted in its correct position in the sorted list. This process is repeated until all elements in the list are in their correct positions and the list is sorted.

Insertion sort has a time complexity of O(n^2), which means it is not the most efficient sorting algorithm for large lists. However, it is simple to implement and can be useful for small lists or partially sorted lists.

Using Recursion

def insertion_sort_recursive(arr, n):
    # Base case: the list is already sorted
    if n <= 1:
        return
    
    # Sort the first n-1 elements
    insertion_sort_recursive(arr, n-1)
    
    # Insert the last element in its correct position
    last = arr[n-1]
    j = n-2
    while j >= 0 and arr[j] > last:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = last

# Test the function
arr = [5, 2, 4, 6, 1, 3]
insertion_sort_recursive(arr, len(arr))
print(arr)  # Output: [1, 2, 3, 4, 5, 6]

This recursive implementation of insertion sort works by dividing the list into two sublists: the first n-1 elements, and the last element. The function recursively sorts the first n-1 elements, and then inserts the last element in its correct position in the sorted list.

The time complexity of this recursive implementation of insertion sort is still O(n^2), because the function makes O(n) recursive calls, and each call takes O(n) time to insert the last element in its correct position. However, the recursive implementation can be more difficult to understand and may not be as efficient as the iterative implementation.