An integer array arr is given. Rearrange all values in non-decreasing order by applying the insertion sort algorithm.
During every pass, the current value from the unsorted part must be inserted into the correct position inside the sorted prefix. Return the sorted array.
Example 1
Input: arr = [12, 11, 13, 5, 6]
Output: [5, 6, 11, 12, 13]
Explanation: Value 11 is inserted before 12, value 13 remains after the sorted prefix, value 5 moves to the front, and value 6 is inserted after 5.
Example 2
Input: arr = [4]
Output: [4]
Explanation: A single value already forms a sorted array, so no shift or insertion is required.
Approach
Insertion sort treats the first element as sorted, then places each next element in its correct position within the sorted left part.
Larger elements are shifted one position right to create space for the current value.
It works well for sorted or nearly sorted arrays because only a few shifts are needed. In a reverse-sorted array, each new element must move past all previous elements, causing many comparisons and shifts.
Algorithm
The array length
nis stored so every value after the first position can be processed as a key value.Every index from
1throughn - 1is visited, andarr[index]is stored askeybecause the sorted prefix may be shifted.A pointer named
positionis placed atindex - 1so the sorted prefix can be scanned from right to left.Larger prefix values are shifted one position toward the right while
positionstays valid andarr[position]remains greater thankey.The
positionpointer is moved left after every shift so the next larger prefix value can be checked.The
keyvalue is written atposition + 1, because the loop stops just before the correct insertion slot.The sorted array is returned after every key value has been inserted into the sorted prefix.
Dry Run
Insertion Sort
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts an integer array by inserting every key into a sorted prefix. vector<int> insertionSort(vector<int>& arr) { int n = arr.size(); // Every pass inserts one key value into the sorted prefix. for (int index = 1; index < n; index++) { int key = arr[index]; int position = index - 1; // Shift larger values right to create the insertion slot. while (position >= 0 && arr[position] > key) { arr[position + 1] = arr[position]; position--; } // Place the key after the last value not greater than it. arr[position + 1] = key; } return arr; }};// Driver codeint main() { // Input array vector<int> arr = {12, 11, 13, 5, 6}; // Solution object creation Solution obj; // Result printing vector<int> answer = obj.insertionSort(arr); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N2) in the average and worst cases because each key can shift across a sorted prefix of size up to N - 1. The best case is O(N) when the array is already sorted, because each key needs only one comparison and no shift.
Space Complexity: O(1) auxiliary space, because only key, position, and loop variables are maintained. The input array is rearranged in place.
Interview follow-up Questions
Yes. Equal values are not shifted across each other because the shift condition uses arr[position] > key, not arr[position] >= key. Equal values keep original relative order.
Be the first to add a comment.