Given an array arr[] of positive integers, sort the array in nondecreasing…
2025
Given an array arr[] of positive integers, sort the array in nondecreasing order using the insertion sort algorithm and print the sorted array.
Input format
The first line contains a single integer n — the number of elements in arr[].
The second line contains n space-separated integers arr[0], arr[1], …, arr[n-1].
Output format
Print the n elements of the sorted array in nondecreasing order, separated by single spaces, on one line.
Examples
Input:
5
4 1 3 9 7
Output:
1 3 4 7 9
Explanation: The sorted array is 1 3 4 7 9.Input:
10
10 9 8 7 6 5 4 3 2 1
Output:
1 2 3 4 5 6 7 8 9 10
Explanation: The sorted array is 1 2 3 4 5 6 7 8 9 10.Input:
3
4 1 9
Output:
1 4 9
Explanation: The sorted array is 1 4 9.
Constraints
1 ≤ n ≤ 1000
1 ≤ arr[i] ≤ 10000
Attempted by 4 students.
Show answer & explanation
Concept
Insertion sort maintains a sorted prefix. At iteration i, the element at index i is saved as the key; larger elements in the sorted prefix are shifted one position right until the key can be inserted. The invariant is that arr[0..i] is sorted after iteration i.
Application
For [4, 1, 3, 9, 7], process the array as follows:
Save 1 as the key, shift 4 right, and insert 1 at index 0, giving [1, 4, 3, 9, 7].
Save 3 as the key, shift 4 right, and insert 3 after 1, giving [1, 3, 4, 9, 7].
The key 9 is already at its insertion position, so the array remains [1, 3, 4, 9, 7].
Save 7 as the key, shift 9 right, and insert 7 after 4, giving [1, 3, 4, 7, 9].
Cross-check
The result is nondecreasing and contains exactly the same multiset of values as the input. The algorithm uses O(n2) time in the worst case and O(1) auxiliary space.