Trusted answers to developer questions

How to implement insertion sort in Python

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

Algorithm

  1. Choose a key, starting from index 11 to n−1n-1, where nn is the length of the array.

  2. 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 00 is reached.

  3. Select the next index as the key. Repeat step 2.

Dry run

Set key = index 1
1 of 17

Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        # Set key:
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            # Swap:
            arr[j + 1] = arr[j]
            arr[j] = key
            
            # Decrement 'j':
            j -= 1
    return arr
array = [5, 2, 12, 12, 1]
print("Original array: %s" % array)
print("Sorted array: %s" % insertion_sort(array))

RELATED TAGS

implement
insertion
sort
python
algorithm
Copyright ©2024 Educative, Inc. All rights reserved
Keep Exploring
Related Courses

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

TRENDING TOPICS

Learn to Code

Tech Interview Prep

Generative AI

Data Science

Machine Learning

GitHub Students Scholarship

Early Access Courses

Pricing

For Individuals

Try for Free

Gift a Subscription

CONTRIBUTE

Become an Author

Become an Affiliate

Earn Referral Credits

RESOURCES

Blog

Cheatsheets

Webinars

Answers

ABOUT US

Our Team

Careers

Hiring

Frequently Asked Questions

Contact Us

Press

LEGAL

Privacy Policy

Cookie Policy

Terms of Service

Business Terms of Service

Data Processing Agreement

Copyright ©2024 Educative, Inc. All rights reserved.

soc2
Did you find this helpful?