Java merge sort algorithm example

by

Sorting algorithm

A sorting algorithm is a way to put elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (like search and merge algorithms) which require input data to be in sorted lists. It is also often useful for canonicalizing data and for producing human-readable output.

The output must satisfy following two conditions:

  • The output is in no decreasing order i.e.each element is no smaller than the previous element according to the desired total order.
  • The output is a reordering of elements but with all of the original elements of the input.

Merge sort

Merge Sort works on Divide and Conquer algorithm technique. It is one of the most popular sorting algorithms. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. It will be the sorted list.

Example

package com.w3schools;
 
public class Test {
	private int data[];
        private int length;
        private int[] tempArray;
 
	public void sort(int inputData[]) {
		this.data = inputData;
                this.length = inputData.length;
                this.tempArray = new int[length];
                mergeSort(0, length - 1);
	}
 
	private void mergeSort(int lowerIndex, int higherIndex) {        
	   if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            //Sorts the left side of the array
            mergeSort(lowerIndex, middle);
            //Sorts the right side of the array
            mergeSort(middle + 1, higherIndex);
            //Merge both sides
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }
 
    private void mergeParts(int lowerIndex, int middle, int higherIndex) {		 
        for (int i = lowerIndex; i <= higherIndex; i++) {
        	tempArray[i] = data[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempArray[i] <= tempArray[j]) {
            	data[k] = tempArray[i];
                i++;
            } else {
            	data[k] = tempArray[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            data[k] = tempArray[i];
            k++;
            i++;
        } 
    }
 
    private static void printNumbers(int[] data) {          
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]);
            if(i != data.length-1){
            	System.out.print(", ");
            }
        }
        System.out.println("\n");
    }
 
	public static void main(String args[]){
		Test test = new Test();
		int[] data = {38, 27, 43, 3, 9, 82, 10}; 
		//Print array elements
		printNumbers(data);
		test.sort(data);  
		//Print sorted array elements
		printNumbers(data);
	}
}

Output

38, 27, 43, 3, 9, 82, 10
 
3, 9, 10, 27, 38, 43, 82