How to implement Merge Sort in java

How to implement Merge Sort in java

Merge sort is a divide and conquer algorithm which divide original data into smaller sets of data to solve the problem. In merge sort elements in the collection are divided into two part from middle which produce two collections into left and right parts. The resulting collections are again recursively splitted until they are broke into single element in the collection.

After split process, elements in each collection merge into third collection to produce sorted collection. To merge each elements, it picks the object which is smaller and inserts into new collection. For this collection it now selects the next elements and selects the smaller element from both collection by comparing one element from each collection at a time. This process is recursively done for all collections which were created during split process to produce sorted collection.

Performance of Merge Sort

  • Best Case performance          :    O(n log n) or O(n)
  • Average Case performance   :    O(n log n)
  • Worst Case performance       :    O(n log n)

Understand Merge Sort with an example.

mergesort

Let us see how this can be implemented in Java.

package com.code2succeed.sorting;

import java.util.Arrays;

public class MergeSortExample {
	private static int [] a = {10, 5, 87, 32, 14, 22};
	private int [] tempArray = null;
	public void mergeSort(int [] a) {
		int length = a.length;
		tempArray = new int[length];
		split(0, length-1);
	}
	
	public void split(int lowerIndex, int upperIndex) {
		if(lowerIndex < upperIndex) {
			int middle = lowerIndex + (upperIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
			split(lowerIndex, middle);
            // Below step sorts the right side of the array
			split(middle + 1, upperIndex);
            // Now merge both sides
            merge(lowerIndex, middle, upperIndex);
		}
	}
	
	public void merge(int lowerIndex, int middle, int upperIndex) {
		for (int i = lowerIndex; i <= upperIndex; i++) {
			tempArray[i] = a[i];
        }

        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= upperIndex) {
            if (tempArray[i] <= tempArray[j]) {
                a[k] = tempArray[i];
                i++;
            } else {
                a[k] = tempArray[j];
                j++;
            }
            k++;
        }

        while (i <= middle) {
            a[k] = tempArray[i];
            k++;
            i++;
        }
	}
	
	public void print(int [] a) {
		System.out.println(Arrays.toString(a));
	}
	
	public static void main(String[] args) {
		MergeSortExample mergeSortExample = new MergeSortExample();
		System.out.println("Array Before Sorting : ");
		mergeSortExample.print(a);
		mergeSortExample.mergeSort(a);
		
		System.out.println("Array After Sorting : ");
		mergeSortExample.print(a);
	}
}

Output

Array Before Sorting : 
[10, 5, 87, 32, 14, 22]
Array After Sorting : 
[5, 10, 14, 22, 32, 87]

Leave a Reply

Your email address will not be published. Required fields are marked *