concept · INFO-CS-ADS-131Insertion Sort
Insertion Sort builds a sorted section one element at a time by inserting each new element into its correct position among previously processed elements. It performs particularly well on small and nearly sorted datasets.
Explanation
Overview
Insertion Sort is a comparison-based sorting algorithm that divides a collection into a sorted prefix and an unsorted suffix. It takes the next element from the unsorted section and inserts it into the appropriate position in the sorted section.
Purpose
It is designed for small datasets, nearly sorted collections, and situations where a simple adaptive in-place sorting method is desirable.
Working principle
The algorithm assumes the first element is already sorted. It then selects each subsequent element as a key, shifts larger elements one position to the right, and inserts the key into the resulting gap.
Key concepts
name: Core idea; description: The central focus of insertion sort is the capability described here: Insertion Sort builds a sorted section one element at a time by inserting each new element into its correct position among previously processed elements. It performs particularly well on small and nearly sorted datasets.; name: Problem context; description: Insertion Sort is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using insertion sort, check its assumptions, input requirements, expected output, and resource constraints.
Space complexity
O(1) auxiliary space for the standard iterative implementation.
Example
Consider [7, 3, 5, 2]. The algorithm begins with [7] as the sorted section. It inserts 3 before 7, then inserts 5 between 3 and 7, and finally inserts 2 at the beginning. The result is [2, 3, 5, 7].
Pseudocode
INSERTION_SORT(A):
for i = 1 to length(A) - 1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
return A
Example or application
Consider [7, 3, 5, 2]. The algorithm begins with [7] as the sorted section. It inserts 3 before 7, then inserts 5 between 3 and 7, and finally inserts 2 at the beginning. The result is [2, 3, 5, 7].
Definition
Insertion Sort is a comparison-based sorting algorithm that divides a collection into a sorted prefix and an unsorted suffix. It takes the next element from the unsorted section and inserts it into the appropriate position in the sorted section.
Purpose
It is designed for small datasets, nearly sorted collections, and situations where a simple adaptive in-place sorting method is desirable.
Working Principle
The algorithm assumes the first element is already sorted. It then selects each subsequent element as a key, shifts larger elements one position to the right, and inserts the key into the resulting gap.
Algorithm Steps
Treat the first element as a sorted section.
Select the next element as the key.
Compare the key with elements in the sorted section from right to left.
Shift elements larger than the key one position to the right.
Insert the key into the empty position.
Expand the sorted section by one element.
Repeat until the entire collection is sorted.
Pseudocode
INSERTION_SORT(A):
for i = 1 to length(A) - 1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
return A
Best Case
O(n) time when the array is already sorted because each new element requires only one comparison with its predecessor.
Average Case
O(n²) time for randomly arranged data because elements may need to be shifted across a substantial portion of the sorted prefix.
Worst Case
O(n²) time when the array is in reverse order because each new element must be shifted past all previously processed elements.
Space Complexity
O(1) auxiliary space for the standard iterative implementation.
Stability
Insertion Sort is stable when it shifts elements only while their keys are strictly greater than the key being inserted. Equal-key elements therefore retain their original relative order.
In Place Property
Insertion Sort is in-place because it rearranges elements directly within the original array using a small number of temporary variables.
Adaptive Behavior
Insertion Sort is adaptive because its running time depends on how far elements must move. Nearly sorted data generally requires fewer shifts than randomly arranged or reverse-sorted data.
Online Property
Insertion Sort is an online sorting algorithm in the sense that it can process elements as they arrive, inserting each new element into an already sorted prefix.
Number Of Shifts
The number of shifts depends on the input arrangement. In the worst case, the algorithm may perform approximately n(n - 1) / 2 shifts.
Advantages
Easy to implement.
Efficient for small datasets.
Performs well on nearly sorted arrays.
Stable when implemented with strict greater-than comparisons.
Uses constant auxiliary memory.
Can process elements incrementally.
Limitations
O(n²) average and worst-case time complexity.
Requires many shifts for reverse-sorted data.
Usually becomes inefficient for large randomly arranged arrays.
Array insertions may require moving multiple elements.
Comparison With Selection Sort
Insertion Sort moves elements to create the correct position for each key, while Selection Sort scans the unsorted portion to find the minimum. Insertion Sort can benefit from nearly sorted input, whereas Selection Sort generally performs the same number of comparisons regardless of input order.
Practical Applications
Sorting small arrays.
Sorting nearly sorted data.
Maintaining a sorted collection as new elements arrive.
Serving as a small-array optimization inside hybrid sorting algorithms.
Sorting short sequences of records.
Common Errors
Overwriting the key before it has been saved.
Using an incorrect loop boundary when shifting elements.
Failing to insert the key after the shifting process.
Using greater-than-or-equal comparison and unintentionally making the algorithm unstable.
Accessing an invalid array position after the left boundary is crossed.
Implementation Considerations
The key must be stored before shifting begins. The shifting loop must stop when it reaches the beginning of the array or encounters an element that is not greater than the key.
Key Takeaway
Insertion Sort builds a sorted prefix by inserting elements into their correct positions. Its simplicity, stability, and strong performance on nearly sorted data make it valuable for small collections and hybrid sorting implementations.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of insertion sort is the capability described here: Insertion Sort builds a sorted section one element at a time by inserting each new element into its correct position among previously processed elements. It performs particularly well on small and nearly sorted datasets. |
Problem context | Insertion Sort is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using insertion sort, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of insertion sort? | Insertion Sort builds a sorted section one element at a time by inserting each new element into its correct position among previously processed elements. It performs particularly well on small and nearly sorted datasets. |
What should be checked before applying insertion sort? | For insertion sort, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of insertion sort be validated? | Trace a representative insertion sort case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of insertion sort.
Identify the assumptions, inputs, and conditions relevant to insertion sort.
Evaluate an application of insertion sort for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures