✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-131

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.

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

NameDescription

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

QuestionAnswer

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