Java Program for Merge Sorting

What is merge sort ?

Merge sort is a divide-and-conquer algorithm, here breaking down a list into multiple sub lists till each sub list consists of a single element and then merging all sub lists in order to get a sorted list.

Merge Sort Algorithm

Divide the unsorted list into multiple sub lists using mid index ( ( start index + end index) /2) until each sub list contains single element.

Take two adjacent pairs of sub list and merge them as list of 2 elements.

Repeat step 2 process till merging single sorted list of all elements.

Merge Sorting Steps

Merge Sorting Time complexity

Number of elements in the list is N, N is divided into a max of log N sub lists, and merging all sub lists into a single list takes O(N) time, Worst case run time O(N Log N).

Merge Sorting Java Program

import java.util.Scanner;

public class MergeSortingTest {
	
	public static void mergeList(int[] listVals, int startIndex, int midIndex, int endIndex){
		// Starting position of both parts 
		int p = startIndex;
		int q = midIndex + 1;
		int[] sortedListVals = new int[(endIndex-startIndex)+1];
		for(int i=startIndex, index = 0;i<=endIndex;i++,index++){
			// Checks whether 1st part is end or not.
			if(p > midIndex){
				sortedListVals[index] = listVals[q];
				q += 1;
			}
			// Checks whether 2nd part is end or not. 
			else if(q > endIndex){
				sortedListVals[index] = listVals[p];
				p += 1;
			}
			// Checks which part has smaller element.
			else if(listVals[p] < listVals[q]){
				sortedListVals[index] = listVals[p];
				p += 1;
			}
			else {
				sortedListVals[index] = listVals[q];
				q += 1;
			}
		}
		for( p=0;p<sortedListVals.length;p++){
			listVals[startIndex] = sortedListVals[p];
			startIndex += 1;
		}
	}
	
	public static void mergeSort(int[] listVals, int startIndex, int endIndex){
		if(startIndex < endIndex){
			// finding mid index 
			int midIndex = (startIndex+endIndex)/2;
			// Sorting 1st part of the array.
			mergeSort(listVals, startIndex, midIndex);
			// Sorting 2nd part of the array.
			mergeSort(listVals, midIndex+1, endIndex);
			// merge the both parts, comparing elements 
			mergeList(listVals, startIndex, midIndex, endIndex);
		}
	}

	public static void main(String[] args){
	    int[] numberList;
	    Scanner in = new Scanner(System.in); 
	    System.out.println("Merge Sorting");
	    System.out.println("--------------------");
	    System.out.println("Enter numbers count: ");                   
	    int count = in.nextInt();                   
	    numberList = new int[count];
	    System.out.println("Enter numbers: "); 
	    for (int i=0;i<count;i++){
	    	numberList[i]=in.nextInt();
	    }
	    in.close();
	    mergeSort(numberList, 0, numberList.length-1);
	    
	    System.out.println("Sorted numbers: "); 
	    for(int number : numberList){
	    	System.out.print(number+"\t");
	    }
	}
}                                                                                                                                            

$ javac MergeSortingTest.java
$ java MergeSortingTest  
Merge Sorting
--------------------
Enter numbers count: 
5
Enter numbers: 
24
13
17
11
5
Sorted numbers: 
5	11	13	17	24