Merge Sort Example Java Program


Definition

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Conceptually, a merge sort works as: Divide the unsorted list into n sublists, each containing 1 element and repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Merge Sort Example Program

import java.util.Arrays;
public class MergeSort {
	private int[] arr;
    private int[] tempArr;
    private int length;
    public static void main(String a[]){
        int[] arr = {67,89,32,76,41,99,12,05,40,53};
		System.out.println("Array before sorting is ");
		for(int i=0;i < arr.length;i++){
		System.out.println(arr[i]);
		}		
        MergeSort mers = new MergeSort();
        mers.sort(arr);
		System.out.println("Array after sorting is ");
        for(int i:arr){
            System.out.println(i);
        }
    }
    public void sort(int arr[]) {
        this.arr = arr;
        this.length = arr.length;
        this.tempArr = new int[length];
        MergeMethod1(0, length - 1);
    }
    private void MergeMethod1(int lowIndex, int highIndex) {
        if (lowIndex < highIndex) {
            int middle = lowIndex + (highIndex - lowIndex) / 2;
            MergeMethod1(lowIndex, middle);
            MergeMethod1(middle + 1, highIndex);
            mergeMethod2(lowIndex, middle, highIndex);
        }
    }
    private void mergeMethod2(int lowIndex, int middle, int highIndex) {
        for (int i = lowIndex; i <= highIndex; i++) {
            tempArr[i] = arr[i];
        }
        int i = lowIndex;
        int j = middle + 1;
        int k = lowIndex;
        while (i <= middle && j <= highIndex) {
            if (tempArr[i] <= tempArr[j]) {
                arr[k] = tempArr[i];
                i++;
            } else {
                arr[k] = tempArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            arr[k] = tempArr[i];
            k++;
            i++;
        }
 
    }
}

Sample Output

Output is:
Array before sorting is
67
89
32
76
41
99
12
05
40
53
Array after sorting is
05
12
32
40
41
53
67
76
89
99