Insertion is one of the basic sorting algorithms. This sorting technique takes elements one by one from the list (array) and inserts them in the correct order in the new sorted list.

In the insertion sort algorithm, every step moves an element from the unsorted section (subarray) to the sorted section (subarray) until all the elements are sorted in the list.

To understand the working of the insertion sort, let’s check the algorithm.

**Step 1:**Assume that the first element in the list is in the sorted section of the list and remaining all elements are in the unsorted section.**Step 2:**Consider the first element from the unsorted list and insert that element into the sorted list in the order specified (ascending or descending)**Step 3:**Repeat the above steps until all the elements from the unsorted list are moved to the sorted list.

This is one of the very important data structure coding interview questions.

If you understand the algorithm, you can write code in any programming language.

**Prerequisite:**

- In the below Python code, we are using Python while and for a loop.
- Python list to store the elements to sort.

**Python Code with Example:**

# This function takes unsorted array as an input # and returns sorted array. def insertion_sort(arr): #loop over all the elements in the list for i in range(1, len(arr)): val = arr[i] # move elements of list [0..i-1], that are # greater than val, to one position ahead # of the current position j = i-1 while j >=0 and val < arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = val return arr #given array arr = [74, 14, 13, 42, 7] sorted_arr = insertion_sort(arr) print(sorted_arr)

**Output:**

[7, 13, 14, 42, 74]

Here is the execution of insertion sort at each stage (iteration).

By tweaking few lines of code, we can also sort the string in Python.

# This function takes unsorted array as an input # and returns sorted array. def insertion_sort(arr): #loop over all the elements in the list for i in range(1, len(arr)): val = arr[i] # move elements of list [0..i-1], that are # greater than val, to one position ahead # of the current position j = i-1 while j >=0 and val < arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = val return arr #given string sample_string = "csestack" arr = [i for i in sample_string] sorted_arr = insertion_sort(arr) print(f"Origional String: {sample_string}") print(f"Sorted String: {''.join(sorted_arr)}")

**Output:**

Origional String: csestack Sorted String: acceksst

To sort the given string, we are converting the string into the list and then sorting the list. The sorted list is converted back into the string.

There are already inbuilt functions to sort the list in Python. But, understanding the algorithm is important. Insertion sort algorithm is asked in many job interviews to test candidate’s logic-building skills and algorithm understanding.

For practice, you can apply insertion sort to sort the characters in the string. Let’s try and share your code in the comment section.

**Check Other Sorting Algorithms:**

This tutorial is all about the simple program for insertion sort in Python using list and string. If you have any doubt, let me know in the comment section.

There are little mistakes in the code for sorting the string

Line 23:

`arr = [i for i in arr]`

instead of`arr = [i for i in sample_string]`

Line 25:

`print("Origional String: " sample_string)`

instead of`print("Original String: ", sample_string)`

Thanks for those corrections. Addressed. I would have liked knowing your real name though 😀 Keep coding!

Updated print statement with

`f-string`

. I think this is the better way of doing it.What is the time complexity of the insertion sort algorithm, and how does it compare to other sorting algorithms?