Merge Sort in JAVA

In this tutorial, we will learn how to perform merge sort in Java. Here you will find the steps we have followed, Java code and the output.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

‘Merge Sort’ uses the following algorithm to sort the elements of an array:
let the array be -> {1,4,0,8}

  1. Split the array into two portions, using the middle element
    can be considered as the middle element of the array
  2. Treat each portion as a separate array and repeat step 1 on it, do this until two elements remain in a sub-portion
    after splitting, the array has two sub-arrays {1,4} and {0,8}
  3. arrange the two elements in each sub-array in ascending (or descending) order
    1<4, so the left sub-array is {1,4}
    0<8, so the right sub-array is {0,8}
  4. Merge the sub-arrays in ascending (or descending) order to get back the sorted array
    {1,4} and {0,8} when merged together give {0,1,4,8}
    Hence, the sorted array is {0,1,4,8}

Java code to perform Merge Sort

import java.util.Scanner;
public class MergeSort
{
void inputArray(int array[],int length)
 {
     Scanner scan=new Scanner(System.in);
     System.out.print("Input "+length+" (integer) elements: ");
     //note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
     for(length--;length>=0;length--){
        array[length]=scan.nextInt();
     }
 }
void printArray(int array[],int length)
 {
     System.out.print("The elements of the given array are: ");
     for(int i=0;i<length;i++)System.out.print(array[i]+" ");
 }
void merge(int array[], int lower, int middle, int upper) 
{ 
    int i, j, k; 
    int left[]=new int[middle-lower+1];//creating sub-array to store elements in the left portion of 'array[]'
    int right[]=new int[upper-middle];//creating sub-array to store elements in the right portion of 'array[]'
    for (i = 0; i < middle-lower+1; i++)//copying appropriate elements from array[] to left[]
    left[i] = array[lower + i];
    for (j = 0; j < upper-middle; j++)//copying appropriate elements from array[] to right[] 
        right[j] = array[middle + 1 + j];
    i = 0; // initial index of sub-array left[] 
    j = 0; // initial index of sub-array right[]
    k = lower; //initial index of merged array 
    for (k=lower;i < middle-lower+1 && j < upper-middle;k++) 
    {//THIS CONDITION SORTS IN ASCENDING ORDER 
        if (left[i] <= right[j]) array[k] = left[i++];//storing value of left[i] in array[k] if the former is smaller
        else array[k] = right[j++];//storing value of right[j] in array[j] if the former is smaller
    }
    while (i < middle-lower+1) array[k++] = left[i++];//copying back the remaining elements of left[] to array[]
    while (j < upper-middle) array[k++] = right[j++];//copying back the remaining elements of right[] to array[]
}
void mergeSort(int array[],int lower,int upper)
 {
     if(lower>=upper)return;//signifies that array contains only one element
     mergeSort(array,lower,(lower+upper)/2);//sorting the left portion of the array
     mergeSort(array,((lower+upper)/2)+1,upper);//sorting the right portion of the array
     merge(array,lower,(lower+upper)/2,upper);//merging the two portions once sorting is done
 }
public static void main(String args[])
{
    MergeSort ob = new MergeSort();
    int array[] = new int[4];
    ob.inputArray(array,4);
    ob.mergeSort(array,0,4-1);//passing 4-1 because array-index-counting starts from 0
    ob.printArray(array,4);
}
}//class ends

Output:

Input 4 (integer) elements: 1 4 0 8
The elements of the given array are: 0 1 4 8

Summary:

  • an object ‘ob’ of the class is created to call the required functions
  • an array ‘array[]’ is initialized with length 4
  • ob.inputArray(int[],int) is called to take input integer elements from the user and store them in the array
  • ob.mergeSort(int[],int,int) is called to sort the elements of the array with the algorithm explained above
  • ob.printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

  • the value ‘4’ can be changed to any other value in order to get the desired array-length
  • since (in JAVA) arrays are passed by reference, therefore the changes made in mergeSort(int[],int,int) and merge(int[],int,int,int) stay permanently
  • to sort in descending order, just change the sign from ‘<=’ to ‘>’ in the logical condition inside the 3rd for loop of merge(int[],int,int,int)

Also learn:





Leave a Reply

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