Sort an integer array using mergesort algorithm in java (with example)

What is merge sort algorithm?

• Merge sort(or MergeSort) is efficient, comparison based algorithm.
• The properties of merge sort algorithm are as follows:
  • MergeSort is divide and conquer algorithm.
  • MergeSort is a stable algorithm, the relative order of equal keys does not changed during sorting.
  • MergeSort requires additional O(n) space, so its not recommended for large data sets.

Time complexity of merge sort algorithm

Program – sort an integer array using mergesort algorithm in java.

package org.learn.arrays;

import java.util.Arrays;

public class MergeSort {

	public static void main(String[] args) {
		int[] example1 = { 10, 7, 25, 20, 12, 9 };
		System.out.println("Unsorted array is : " + Arrays.toString(example1));
		mergeSort(example1);
		System.out.println("Sorted Array is   : " + Arrays.toString(example1));

		System.out.println(7/2);
		int[] example2 = { 5, 4, 3, 2, 1, 0 };
		System.out.println("\nUnsorted array is : " + Arrays.toString(example2));
		mergeSort(example2);
		System.out.println("Sorted Array is   : " + Arrays.toString(example2));
	}

	public static void mergeSort(int[] a) {
		int[] tempArray = new int[a.length];
		sort(a, tempArray, 0, a.length - 1);
	}

	private static void sort(int[] inputArray, int[] tempArray, int left, int right) {
		if (left >= right)
			return;

		int middle = left + (right - left) / 2;
		
		sort(inputArray, tempArray, left, middle);
		sort(inputArray, tempArray, middle + 1, right);
		merge(inputArray, tempArray, left, middle + 1, right);

	}

	private static void merge(int[] finalArray, int[] tempArray, int left, int middle, int secondArrayEnd) {
		int firstArrayEnd = middle - 1;
		int merge = left;
			
		//copy finalArray to tempArray
		while(merge <= secondArrayEnd) {
			tempArray[merge] = finalArray[merge];
			merge++;
		}		
		
		merge = left;
		//merge to finalArray: sorted array
		while (left <= firstArrayEnd && middle <= secondArrayEnd)
			if (tempArray[left] <= tempArray[middle])
				finalArray[merge++] = tempArray[left++];
			else
				finalArray[merge++] = finalArray[middle++];

		//copy remaining element from first half array to finalArray`
		while (left <= firstArrayEnd) // Copy rest of first half
			finalArray[merge++] = tempArray[left++];

		//copy remaining element from second half of array to finalArray
		while (middle <= secondArrayEnd) // Copy rest of right half
			finalArray[merge++] = tempArray[middle++];

	}
}

Output – sort an integer array using mergesort algorithm in java

Unsorted array is : [10, 7, 25, 20, 12, 9]
Sorted Array is   : [7, 9, 10, 12, 20, 25]

Unsorted array is : [5, 4, 3, 2, 1, 0]
Sorted Array is   : [0, 1, 2, 3, 4, 5]