Insertion Sort
Definition
Insertion sort is a simple sorting algorithm where each iteration removes one element from an input data set and inserts it into its correct position within a partially sorted list until all elements are inserted.
Analogy
Think of insertion sort like organizing playing cards in your hand. You start with an empty hand (sorted list) and pick up cards (elements) one by one from the table (input data set), inserting each card into its correct position in your hand.
Related terms
Selection Sort: A sorting algorithm that repeatedly selects the smallest element from the unsorted part and moves it to the sorted part.
Merge Sort: A divide-and-conquer algorithm that divides an array into two halves, sorts them separately, and then merges them back together.
Quick Sort: A divide-and-conquer algorithm that picks an element as a pivot, partitions the array around this pivot, and recursively sorts subarrays before and after the pivot.
"Insertion Sort" appears in:
Study guides (1)
Additional resources (1)
Practice Questions (5)
- What is the time complexity of selection sort and insertion sort in the worst case scenario?
- In insertion sort, when is an element inserted into the sorted subarray?
- Which sorting algorithm is simpler: selection sort or insertion sort?
- How does insertion sort work?
- What is one advantage of insertion sort over selection sort?
Resources
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.