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.