ANALYSIS & DESIGN OF
ALGORITHM
ASSIGNMENT
The Insertion Sort Algorithm
Submitted By:
Niranjan A R
I [Link] Computer Science
Submitted To:
Dr. Mohammed Sirajudeen M
PG Department of Computer Science
Date of Submission: August 21, 2026
The Insertion Sort Algorithm
1. Introduction
Insertion Sort is a simple and intuitive sorting algorithm that builds a sorted sequence one
element at a time. The algorithm divides the array into two portions: a sorted portion on the left
and an unsorted portion on the right. At each step, it takes the next element from the unsorted
portion, compares it with the elements in the sorted portion, and shifts larger elements one position
to the right. The selected element is then inserted into its correct position. This process is repeated
until all elements in the array are sorted.
Insertion Sort is particularly effective for small datasets and arrays that are already partially
sorted. It is also an in-place sorting algorithm, meaning that it rearranges the elements within the
original array without requiring significant additional memory.
2. Pseudocode
The following pseudocode sorts an array A containing N elements in ascending order using
Insertion Sort. It considers the first element as sorted and then inserts each subsequent element
into its correct position within the sorted portion.
INSERTIONSORT(A, N)
i=1
Repeat While i < N
key = A[i]
j=i-1
Repeat While j >= 0 AND A[j] > key
A[j + 1] = A[j]
j=j-1
A[j + 1] = key
i=i+1
3. C++ Implementation
#include <iostream>
using namespace std;
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int N = 7;
for (int i = 1; i < N; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
arr[j + 1] = key;
cout << "Sorted array: ";
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
cout << endl;
return 0;
}
Output
The program sorts the given array in ascending order using the Insertion Sort
algorithm.
Input Array:
64 34 25 12 22 11 90
Output:
Sorted array: 11 12 22 25 34 64 90
How the Program Works
This C++ program sorts an array of numbers from smallest to largest using Insertion Sort.
It starts by considering the first element as the sorted portion of the array. The algorithm then
selects each subsequent element as the key and compares it with the elements before it.
If an element in the sorted portion is larger than the key, it is shifted one position to the right. This
continues until the correct position for the key is found. The key is then inserted into that position.
For example, for the array:
64 34 25 12 22 11 90
The sorting process gradually produces:
64
34 64
25 34 64
12 25 34 64
12 22 25 34 64
11 12 22 25 34 64
11 12 22 25 34 64 90
Unlike Bubble Sort, Insertion Sort shifts elements instead of repeatedly swapping adjacent
elements. This makes it particularly useful for small or partially sorted arrays.
6. Time and Space Complexity
Complexity is expressed using Big O notation, where n represents the number of elements
in the array.
Case Complexity Explanation
Occurs when the array is
already sorted. Each
Best Case O(n) element only needs to be
compared with the previous
element.
Occurs when the elements
are in a random order.
Average Case O(n²) Multiple elements may need
to be shifted for each
insertion.
Occurs when the array is in
reverse order. Each new
element must be compared
Worst Case O(n²)
with and shifted past almost
every element in the sorted
portion.
6.2 Space Complexity
Metric Complexity Explanation
Insertion Sort works in-
place and requires only a
few additional variables
Space Complexity O(1)
such as key and j,
regardless of the size of the
array.
7. Conclusion
Insertion Sort is a simple and efficient sorting algorithm for small and partially sorted
datasets. It works by dividing the array into a sorted and an unsorted portion, then selecting each
element from the unsorted portion and inserting it into its correct position in the sorted portion.
Larger elements are shifted to the right to make space for the selected element.
Insertion Sort has a best-case time complexity of O(n) when the array is already sorted,
while its average-case and worst-case time complexities are O(n²). Its O(1) space complexity
makes it memory-efficient because sorting is performed directly within the original array.
Although Insertion Sort is not suitable for efficiently sorting large datasets, it is valuable
for understanding fundamental sorting concepts such as comparisons, shifting, insertion, loop
operations, and algorithmic complexity. It also performs well when the input data is already nearly
sorted.