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]