Scribd
Upload
6 views6 pages

Insertion Sort Algorithm in Python

The document explains the Insertion Sort algorithm using Python, detailing how it sorts an array by taking one value at a time from the unsorted section and placing it in the correct position within the sorted section. It includes a step-by-step manual run-through of sorting an example array and provides a Python implementation of the algorithm. Additionally, it discusses potential improvements to reduce shifting operations and outlines the time complexity of the Insertion Sort algorithm.

Uploaded by

virajsawant0211
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views6 pages

Insertion Sort Algorithm in Python

The document explains the Insertion Sort algorithm using Python, detailing how it sorts an array by taking one value at a time from the unsorted section and placing it in the correct position within the sorted section. It includes a step-by-step manual run-through of sorting an example array and provides a Python implementation of the algorithm. Additionally, it discusses potential improvements to reduce shifting operations and outlines the time complexity of the Insertion Sort algorithm.

Uploaded by

virajsawant0211
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1/3/26, 11:30 AM Insertion Sort with Python

❯
 Tutorials  References  Exercises  Certificates  Search... Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Hash Tables
Trees
Binary Trees
Binary Search Trees
AVL Trees
Graphs
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Radix Sort
Insertion Sort with Python
Merge Sort COLOR
❮ Previous Next ❯
PICKER
Python MySQL
MySQL Get Started
MySQL Create Database Insertion Sort
MySQL Create Table
MySQL Insert The Insertion Sort algorithm uses one part of the array to hold the sorted values, and the 
other part of the array to hold values that are not sorted yet.


Sort

The algorithm takes one value at a time from the unsorted part of the array and puts it
into the right place in the sorted part of the array, until the array is sorted.

How it works:

1. Take the first value from the unsorted part of the array.
2. Move the value into the correct place in the sorted part of the array.
3. Go through the unsorted part of the array again as many times as there are values.

Manual Run Through


Before we implement the Insertion Sort algorithm in a Python program, let's manually run
through a short array, just to get the idea.

Step 1: We start with an unsorted array.

[Link] 1/6
1/3/26, 11:30 AM Insertion Sort with Python

❯
 Tutorials 
[ 7, 12, 9, 11, 3]
References  Exercises  Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Hash Tables Step 2: We can consider the first value as the initial sorted part of the array. If it is just one
Trees value, it must be sorted, right?
Binary Trees
Binary Search Trees [ 7, 12, 9, 11, 3]
AVL Trees
Graphs
Linear Search Step 3: The next value 12 should now be moved into the correct position in the sorted
part of the array. But 12 is higher than 7, so it is already in the correct position.
Binary Search
Bubble Sort
[ 7, 12, 9, 11, 3]
Selection Sort
Insertion Sort
Quick Sort
Step 4: Consider the next value 9.
Counting Sort
Radix Sort
[ 7, 12, 9, 11, 3]
Merge Sort

Python MySQL Step 5: The value 9 must now be moved into the correct position inside the sorted part of
MySQL Get Started the array, so we move 9 in between 7 and 12.
MySQL Create Database
MySQL Create Table [ 7, 9, 12, 11, 3]
MySQL Insert

Step 6: The next value is 11.

[ 7, 9, 12, > 11, 3]

Step 7: We move it in between 9 and 12 in the sorted part of the array.

[ 7, 9, 11, 12, 3]

Step 8: The last value to insert into the correct position is 3.

[ 7, 9, 11, 12, 3]

Step 9: We insert 3 in front of all other values because it is the lowest value.

[ 3,7, 9, 11, 12]

Finally, the array is sorted.

Run the simulation below to see the steps above animated:

Insertion Sort

[ 7, 12, 9, 11, 3 ]

[Link] 2/6
1/3/26, 11:30 AM Insertion Sort with Python

Implement Insertion Sort in Python Upgrade


❯
 Tutorials  References Exercises  Certificates  Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
To implement the Insertion Sort algorithm in a Python program, we need:
Hash Tables
Trees 1. An array with values to sort.
Binary Trees 2. An outer loop that picks a value to be sorted. For an array with n values, this outer
Binary Search Trees loop skips the first value, and must run n − 1 times.
AVL Trees 3. An inner loop that goes through the sorted part of the array, to find where to insert
Graphs the value. If the value to be sorted is at index i, the sorted part of the array starts at
Linear Search index 0 and ends at index i − 1.
Binary Search
The resulting code looks like this:
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Example Get your own Python Server

Counting Sort Using the Insertion Sort on a Python list:


Radix Sort
Merge Sort mylist = [64, 34, 25, 12, 22, 11, 90, 5]

Python MySQL n = len(mylist)


for i in range(1,n):
MySQL Get Started
insert_index = i
MySQL Create Database current_value = [Link](i)
MySQL Create Table for j in range(i-1, -1, -1):
MySQL Insert if mylist[j] > current_value:
insert_index = j
[Link](insert_index, current_value)

print(mylist)

Run Example »

Insertion Sort Improvement


Insertion Sort can be improved a little bit more.

The way the code above first removes a value and then inserts it somewhere else is
intuitive. It is how you would do Insertion Sort physically with a hand of cards for example.
If low value cards are sorted to the left, you pick up a new unsorted card, and insert it in
the correct place between the other already sorted cards.

The problem with this way of programming it is that when removing a value from the
array, all elements above must be shifted one index place down:

And when inserting the removed value into the array again, there are also many shift
operations that must be done: all following elements must shift one position up to make
place for the inserted value:

[Link] 3/6
1/3/26, 11:30 AM Insertion Sort with Python

❯
 Tutorials  References  Exercises  Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Hash Tables
Trees
Binary Trees
Binary Search Trees These shifting operations can take a lot of time, especially for an array with many
AVL Trees elements.
Graphs
Linear Search
Binary Search
Hidden memory shifts: You will not see these shifting operations happening in the code
Bubble Sort
if you are using a high-level programming language such as Python or JavaScript, but the
Selection Sort shifting operations are still happening in the background. Such shifting operations require
Insertion Sort extra time for the computer to do, which can be a problem.
Quick Sort
Counting Sort
Radix Sort
You can read more about how arrays are stored in memory here.
Merge Sort

Python MySQL
MySQL Get Started
Improved Solution
MySQL Create Database
We can avoid most of these shift operations by only shifting the values necessary:
MySQL Create Table
MySQL Insert

In the image above, first value 7 is copied, then values 11 and 12 are shifted one place up
in the array, and at last value 7 is put where value 11 was before.

The number of shifting operations is reduced from 12 to 2 in this case.

This improvement is implemented in the example below:

Example
Insert the improvements in the sorting algorithm:

mylist = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(mylist)
for i in range(1,n):
insert_index = i
current_value = mylist[i]
for j in range(i-1, -1, -1):
if mylist[j] > current_value:
mylist[j+1] = mylist[j]
insert_index = j
else:
break
mylist[insert_index] = current_value

print(mylist)

[Link] 4/6
1/3/26, 11:30 AM Insertion Sort with Python

Run Example » ❯
 Tutorials  References  Exercises  Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Hash Tables What is also done in the code above is to break out of the inner loop. That is because
Trees there is no need to continue comparing values when we have already found the correct
Binary Trees place for the current value.
Binary Search Trees
AVL Trees
Graphs
Linear Search
Insertion Sort Time Complexity
Binary Search Insertion Sort sorts an array of n values.
Bubble Sort
Selection Sort On average, each value must be compared to about n

2
other values to find the correct
Insertion Sort place to insert it.
Quick Sort
Counting Sort Insertion Sort must run the loop to insert a value in its correct place approximately n
times.
Radix Sort
Merge Sort
We get time complexity for Insertion Sort: O(
n 2
⋅ n) = O(n )
2

Python MySQL The time complexity for Insertion Sort can be displayed like this:
MySQL Get Started
MySQL Create Database
MySQL Create Table
MySQL Insert

For Insertion Sort, there is a big difference between best, average and worst case
scenarios.

Next up is Quicksort. Finally we will see a faster sorting algorithm!

❮ Previous Sign in to track progress Next ❯

-->
 PLUS SPACES GET CERTIFIED FOR TEACHERS

[Link] 5/6
1/3/26, 11:30 AM Insertion Sort with Python

❯
 Tutorials  References 
FOR BUSINESS
Exercises 
CONTACT US
Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Hash Tables
Trees Top Tutorials Top References
Binary Trees
HTML Tutorial HTML Reference
Binary Search Trees CSS Tutorial CSS Reference
JavaScript Tutorial JavaScript Reference
AVL Trees How To Tutorial SQL Reference
Graphs SQL Tutorial Python Reference
Python Tutorial [Link] Reference
Linear Search [Link] Tutorial Bootstrap Reference
Bootstrap Tutorial PHP Reference
Binary Search PHP Tutorial HTML Colors
Java Tutorial Java Reference
Bubble Sort
C++ Tutorial AngularJS Reference
Selection Sort jQuery Tutorial jQuery Reference

Insertion Sort Top Examples Get Certified


Quick Sort HTML Examples HTML Certificate
Counting Sort CSS Examples CSS Certificate
JavaScript Examples JavaScript Certificate
Radix Sort How To Examples Front End Certificate
SQL Examples SQL Certificate
Merge Sort Python Examples Python Certificate
[Link] Examples PHP Certificate
Bootstrap Examples jQuery Certificate
Python MySQL PHP Examples Java Certificate
Java Examples C++ Certificate
MySQL Get Started XML Examples C# Certificate
jQuery Examples XML Certificate
MySQL Create Database
MySQL Create Table
MySQL Insert
     FORUM ABOUT ACADEMY
W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning.
Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness
of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookies and privacy policy.

Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by [Link].

[Link] 6/6

Common questions

Powered by AI

A manual demonstration of Insertion Sort clarifies the thought process behind dynamically creating a sorted segment. It helps visualize the sequence of actions involved in sorting, which is then translated into control structures and operations in programming languages like Python. This comprehension supports writing more intuitive and error-free code .

Manually performing Insertion Sort, we begin with an array like [7, 12, 9, 11, 3]. Step 1: Assume the first element (7) is sorted. Step 2: Consider the next element (12), already correctly placed as 12 > 7. Step 3: Take 9, compare it with 12 and 7, and place it between 7 and 12. Proceed similarly for 11 and 3, inserting them into their correct locations among the sorted elements. This illustrates systematically placing each element into its correct position, expanding the sorted portion .

The improved implementation of Insertion Sort in Python minimizes shifting operations by only shifting elements when necessary. Instead of removing and reinserting elements (which involves multiple shifts), the algorithm shifts elements directly in place when moving a new element into the sorted portion. This reduces time-consuming memory shifts and enhances efficiency by decreasing the number of operations required, particularly on large datasets .

Improved Insertion Sort reduces the number of shifting operations by shifting elements only when necessary and places the current element directly where it belongs. This contrasts with regular implementations that remove and reinsert elements, necessitating more shifts. The improved method is more efficient in terms of time, resulting in a significantly faster execution on average .

Insertion Sort has a worst-case time complexity of O(n^2) that arises when the array is sorted in reverse order, requiring each new element to be compared against all previously sorted elements. Conversely, the best-case scenario occurs when the array is already sorted, reducing the time complexity to O(n) because each element only needs to be compared once .

In Insertion Sort, shifting elements is integral to placing each unsorted element into its correct position within the sorted portion of the array. Each insertion could require shifting all subsequent elements, leading to O(n^2) time complexity, significantly affecting performance as the array size increases. Optimizing this step, by minimizing shifts, can improve the algorithm's efficiency .

Although Insertion Sort has a simpler implementation, it is slower (O(n^2)) on larger datasets compared to efficient algorithms like Quick Sort (O(n log n)). However, Insertion Sort performs better on small or partially sorted datasets due to reduced overhead. The trade-off lies in the need for a faster algorithm like Quick Sort for large, unsorted datasets, while Insertion Sort may be preferred for its simplicity and use in educational contexts .

In the improved Insertion Sort, breaking out of the inner loop as soon as the correct insertion point is found prevents unnecessary comparisons with elements of the sorted array. This reduces the number of operations per insertion, thereby optimizing the runtime efficiency especially in partially sorted datasets where the insertion point is often reached early in the inner iteration .

High-level languages like Python or JavaScript abstract away the shifting operations involved during Insertion Sort, thus, these operations are performed seamlessly in the background. This abstraction is convenient for developers, but it also hides performance details, such as the numerous shift operations that can slow down the algorithm on large arrays due to the time required for memory manipulation .

The Insertion Sort algorithm involves key stages that ensure the sorting of an array. Initially, the algorithm starts by assuming that the first element is sorted. As each element from the unsorted part is considered, it gets placed into its correct position in the already sorted part of the array. The algorithm effectively compares an element with those in the sorted part and shifts larger elements to make space for insertion. This is repeated until all elements are sorted .

You might also like