28. Sort an Array

Topic :

arrays

Difficulty :

medium

Problem Link :

problem statement

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not 
changed (for example, 2 and 3), while the positions of other numbers are 
changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

Constraints:

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

solution

USING EXTRA SPACE

import java.io.*;
import java.util.*;
 class MergeSort
{
  public static void main (String args[])
  { int nums[]={8,3,4,12,5,6};
    nums=mergeSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  static int[] mergeSort(int nums[])
  {
      int n=nums.length;
      if(n==1){
       return nums;}
      
      int  mid=n/2;
      int left[]=mergeSort(Arrays.copyOfRange(nums,0,mid));
      int right[]=mergeSort(Arrays.copyOfRange(nums,mid,n));
      
      return merge(left,right);
    }
   static int[] merge(int left[], int right[])
   {
      int mergedArray[]=new int[left.length+right.length];
      int i=0;
      int j=0;
      int k=0;
      
      while(i<left.length && j<right.length){
          
          if(left[i]<=right[j]){
            mergedArray[k++]=left[i++];
            }
          
          else{
              mergedArray[k++]=right[j++];
            }
     } 
     
     while(i<left.length){
         mergedArray[k++]=left[i++];
        }
     while( j<right.length){
         mergedArray[k++]=right[j++];
        } 
     return mergedArray;
  }
}

IN PLACE

import java.io.*;
import java.util.*;
 class MergeSort_InPlace
{
  public static void main (String args[])
  { int nums[]={8,3,4,12,5,6};
    mergeSort(nums,0,nums.length);
    System.out.println(Arrays.toString(nums));
  }
  static void mergeSort(int nums[],int start, int end)
  {
      int n=nums.length;
      if(end-start==1){
       return;}
      
      int  mid=(start+end)/2;
      mergeSort(nums,start,mid); 
      mergeSort(nums,mid,end);
      
      merge(nums,start,mid,end);
    }
   static void merge(int nums[], int start, int mid , int end)
   {
      int mergedArray[]=new int[end-start];
      int i=start;
      int j=mid;
      int k=0;
      
      while(i<mid && j<end){
          
          if(nums[i]<=nums[j]){
            mergedArray[k++]=nums[i++];
            }
          
          else{
              mergedArray[k++]=nums[j++];
            }
     } 
     
     while(i<mid){
         mergedArray[k++]=nums[i++];
        }
     while( j<end){
         mergedArray[k++]=nums[j++];
        } 
    
     for(int it=0;it<mergedArray.length;it++)
     { nums[start+it]=mergedArray[it];
        }
  }
}

TIME COMPLEXITY: O(NlogN)