Introduction

Insertion Sort is a simple and efficient sorting algorithm for small datasets.

The idea is:

  • build sorted portion gradually
  • insert each element
    into its correct position

It works similarly to:

  • arranging playing cards in hand

This problem helps in understanding:

  • sorting fundamentals
  • shifting elements
  • insertion logic
  • partially sorted arrays

Example

Input:arr = [5, 2, 4, 6, 1, 3]
Output:
[1, 2, 3, 4, 5, 6]

Explanation:
Each element is inserted into correct position inside sorted portion.
Constraints
 1 <= arr.length <= 10^5-10^4 <= arr[i] <= 10^4

Approach 1 : Basic Insertion Sort

Explanation

The simplest way to sort using Insertion Sort is:

  1. Assume first element is sorted
  2. Pick next element
  3. Insert it into correct position
    inside sorted portion
  4. Repeat for all elements

After every pass:

  • left portion remains sorted

Steps

  1. Start from second element.
  2. Store current element.
  3. Shift larger elements right.
  4. Insert current element.
  5. Continue traversal.

Dry Run

Input:[5, 2, 4, 6, 1, 3]
Pass 1:
Current element:
2
Shift 5 right
Insert 2

Array becomes:
[2, 5, 4, 6, 1, 3]

Pass 2:
Current element:
4
Shift 5 right
Insert 4

Array becomes:
[2, 4, 5, 6, 1, 3]

Continue remaining passes...

Final Result:
[1, 2, 3, 4, 5, 6]

Basic Insertion Sort Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
Elements may require repeated shifting.

Space Complexity: O(1)
Explanation:
Sorting is performed in-place.

Approach 2 : Optimized Insertion Sort

Explanation

Insertion Sort performs efficiently for:

  • nearly sorted arrays

Optimization idea:

  • stop shifting immediately
    when correct position is found

This reduces unnecessary comparisons.

Steps

  1. Traverse array.
  2. Store current element.
  3. Shift larger elements only.
  4. Stop early if position correct.
  5. Insert element.

Dry Run

Input:[1, 2, 3, 5, 4]

Pass 1:
Current element:
2
Already greater than 1
No shifting needed

Pass 2:
Current element:
3
Already greater than 2
No shifting needed

Pass 4:
Current element:
4
Shift 5 right
Insert 4

Final Result:
[1, 2, 3, 4, 5]

Optimized Insertion Sort Code

Complexity Analysis

Best Case Time Complexity: O(n)Explanation:Already sorted arrays require minimal shifting.

Average Case Time Complexity: O(n²)

Worst Case Time Complexity: O(n²)

Space Complexity: O(1)
Explanation:
Sorting is performed in-place.

Edge Cases

  1. Empty array
  2. Single element array
  3. Already sorted array
  4. Reverse sorted array
  5. Duplicate elements present

Why This Problem is Important

Insertion Sort helps in understanding:

  1. Sorting fundamentals
  2. Element shifting
  3. Insertion logic
  4. Partially sorted arrays
  5. In-place sorting

It is one of the most important beginner sorting algorithms.

Real-World Applications

Insertion Sort concepts are used in:

  1. Small datasets
  2. Hybrid sorting algorithms
  3. Online sorting systems
  4. Educational visualization
  5. Nearly sorted data handling

Common Mistakes

  1. Incorrect shifting logic
  2. Wrong insertion position
  3. Forgetting key storage
  4. Index out of bounds errors

Interview Tips

Interviewers often expect:

  1. Sorting fundamentals
  2. Shifting explanation
  3. Best case optimization understanding

Always explain why:

  • left portion remains sorted
    after every iteration

Related Questions

  1. Bubble Sort
  2. Selection Sort
  3. Merge Sort
  4. Quick Sort
  5. Sort Colors

Final Takeaway

Insertion Sort is a fundamental comparison-based sorting algorithm that teaches element shifting and insertion techniques. Understanding Insertion Sort builds a strong foundation for advanced sorting algorithms and interview problems.