SORT THE HALF SORTED in java

Given an integer array of which both the first half and second half are sorted. The task is to merge two sorted halves of the array into a single sorted array.

Note: The two halves can be of arbitrary sizes.

Input Format

line 1: contains an integer n denoting the size of the array.

line 2: contains n-spaced integers denoting elements of the array.

Output Format

Print an array consisting of n elements denoting the sorted array.

Example 1

Input

6
2 3 8 -1 7 10

Output

-1 2 3 7 8 10

Explanation

The first half sorted array is 2 3 8 and the second half is -1 7 10 and if we merge them and sort them we will get -1 2 3 7 8 10

Example 2

Input

5
3 4 0 1 2

Output

0 1 2 3 4

Explanation

The first half sorted array is 3 4 and the second half is 0 1 2 and if we merge them and sort them we will get 0 1 2 3 4

Constraints

1<=n<=10^5

-10^6<=arr[i]<=10^6

Expected Time Complexity: O(N)

Expected Space Complexity: O(N)

Solution of SORT THE HALF SORTED in java:–

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();

      int arr[] = new int[n];
      for(int i=0;i<n;i++)
        {
          arr[i]=sc.nextInt();
        }

       
       for(int i=0;i<n-1;i++)
        {
           if(arr[i]>arr[i+1])
           {
              int temp=arr[i];
              arr[i]=arr[i+1];
              arr[i+1]=temp;
             
              i=-1;
           }
        }

      for(int i=0;i<n;i++)
        {
          System.out.print(arr[i]+" ");
        }
	}
}