| CARVIEW |
Select Language
HTTP/2 200
cache-control: public, max-age=300, stale-while-revalidate=604800
referrer-policy: strict-origin-when-cross-origin
x-app-version: v251012-rb-251014-1002
x-content-type-options: nosniff
x-frame-options: SAMEORIGIN
x-xss-protection: 1; mode=block
x-app-type: Learn
x-middleware-rewrite: /answers/howdev/how-to-implement-insertion-sort-in-python
x-nextjs-cache: MISS
etag: W/"228sywemqdqcr0"
content-type: text/html; charset=utf-8
x-cloud-trace-context: 9fd2b2b5f55ff4cdad69b81f042cf36d
date: Tue, 14 Oct 2025 11:17:16 GMT
server: Google Frontend
via: 1.1 google
vary: Accept-Encoding
content-encoding: gzip
x-cache-status: miss
alt-svc: h3=":443"; ma=2592000,h3-29=":443"; ma=2592000
How to implement insertion sort in Python 
How to implement insertion sort in Python
Algorithm
-
Choose a key, starting from index 1 to n−1, where n is the length of the array.
-
Keep swapping the key with all the larger values on its left side until a value less than or equal to the key occurs, or index 0 is reached.
-
Select the next index as the key. Repeat step 2.
Dry run
Set key = index 1
1 of 17
5 > 2 ===> Swap
1 of 17
No more values to check on the left side.
1 of 17
New key = index 2 = 12
1 of 17
5 < 12 ===> Change key
1 of 17
Implementation
def insertion_sort(arr):for i in range(1, len(arr)):# Set key:key = arr[i]j = i - 1while j >= 0 and arr[j] > key:# Swap:arr[j + 1] = arr[j]arr[j] = key# Decrement 'j':j -= 1return arrarray = [5, 2, 12, 12, 1]print("Original array: %s" % array)print("Sorted array: %s" % insertion_sort(array))
Relevant Answers
Explore Courses
Free Resources
Copyright ©2025 Educative, Inc. All rights reserved