Insertion Sort
Practice this coding question on Coding Gurukul.
Problem statement
Given an array of n integers, sort it in nondecreasing order using Insertion Sort. Keep a sorted prefix. Insert each next value into that prefix by shifting larger values right. Print the sorted array. Keep every occurrence of a repeated value. Negative values are allowed. Do not use a library sorting function. O(n^2) time is acceptable. Worked example [5, -2, 5, 0, 1] becomes [-2, 0, 1, 5, 5]. Both copies of 5 remain.
Input format
First line: n. Second line: n integers.
Output format
Print the n sorted integers separated by spaces.
Constraints
1 <= n <= 2000; -10^9 <= a[i] <= 10^9.
Sample input
5 5 -2 5 0 1
Sample output
-2 0 1 5 5
Sign in to run or submit a solution in C++, Java or Python.