easySorting Fundamentals

Insertion Sort

Sort an integer array in nondecreasing order by implementing Insertion Sort. Do not use a built-in sort.

GeeksforGeeks ↗

Work through the cases

3 examples

Input notation

One nonempty line of space-separated integers; at most 1000 values.

Expected result

The sorted values, space-separated.

Case 1

Input

8 3 5 3 -1

Expected output

-1 3 3 5 8

Case 2

Input

2 1

Expected output

1 2

Case 3

Input

0 -2 0 -1

Expected output

-2 -1 0 0

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Maintain a sorted portion while rearranging the remaining values. Worst-case time: O(n²); extra algorithm space: O(1). This lesson practices the named sorting algorithm.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayList<Long> values = new ArrayList<>();
        while (in.hasNextLong()) values.add(in.nextLong());
        long[] a = values.stream().mapToLong(Long::longValue).toArray();
        long n = a[0];
        for(int i=1;i<a.length;i++){long v=a[i];int j=i-1;while(j>=0&&a[j]>v){a[j+1]=a[j];j--;}a[j+1]=v;} for(long v:a)System.out.print(v+" ");
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.