Coding Challenge Day- 18: Problem 2: Implement Merge Sort

Hello! So I’m doing a 30 day coding challenge where I solve a few questions every day and thought of posting them here on my blog so that you guys can join the challenge too!

Welcome to Coding challenge Day 18: Problem 2! Be sure to post your answers, queries etc in the comments!

Problem: Implement Merge Sort

Sample input: Original array: [5, 1, 4, 3, 2]
Output: Sorted array: [1, 2, 3, 4, 5]

Solution:

Here is an amazing video to understand how the logic of Merge sort works:

package sort;

import java.util.Arrays;

public class Program001merge_sort {
	
	public static int[] merge_sort(int array[]){
		
		if( array.length <=1){
			return array;
		}
		
		int mid= array.length/2;
		
		int left[]= new int[mid];
		int right[]= new int[array.length-mid];
		
		for(int i=0; i<mid; i++){
			left[i]= array[i];
		}
		
		for(int j=0; j<right.length; j++){
			right[j]= array[mid+j];
		}
		
		int result[]= new int[array.length];
		
		left= merge_sort(left);
		right= merge_sort(right);
		
		result= merge(left, right);
		
		return result;
		
	}
	
	public static int[] merge (int []left, int []right){
		int result[]= new int[left.length +right.length];
		int i=0, j=0, l=0;
		
		while(i<left.length && j<right.length){
			
			if(left[i]<right[j]){
				result[l++]= left[i++];
			}
			
			else if(left[i]>right[j]){
				result[l++]= right[j++];
			}
			
			else{
				result[l++]= right[j++];
				i++;
			}
			
		}
		
		while(i<left.length){
			result[l++]= left[i++];
		}
		
		while(j<right.length){
			result[l++]= right[j++];
		}
		
		return result;
	}
	
	public static void main (String[] args){
		int array[]={5,1,4,3,2};
		int result[]= new int[array.length];
		
		System.out.println("Original array: " +Arrays.toString(array));
		
		result=merge_sort(array);
		
		System.out.println("Sorted array: "+ Arrays.toString(result));
	}

}

Download Code

Happy Learning!!