Merge Sort Java Example

In computer science, merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm. Divide and conquer algorithms divide the original data into smaller sets of data to solve the problem.

During the Mergesort process the object in the collection are divided into two collections. To split a collection, Mergesort will take the middle of the collection and split the collection into its left and its right part. The resulting collections are again recursively splitted via the Mergesort algorithm until they are broke to single element in each collection.

After splitting each collection, mergesort algorithm start combining all collections obtained via above procedure. To combine both collections Mergesort start at each collection at the beginning. It pick the object which is smaller and inserts this object into the 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 create a collection of sorted elements (subset of all elements which needs to be sorted). This process is recursively done for all available collections obtained in first step i.e. splitting the collections.

Once all elements from both collections have been inserted in the new collection, Mergesort has successfully sorted the collection.

To avoid the creation of too many collections, typically only one new collection is created and the new one and existing one are treated as different collections.

To understand better, look at below diagram which follow above approach.

Merge sort algorithm
Merge sort algorithm

Conceptually, merge sort works as follows in recursive fashion:

  1. Divide the unsorted list into two sublists of about half the size
  2. Sort each of the two sublists
  3. Merge the two sorted sublists back into one sorted list

Merge Sort Example

In below example, we have implemented merge sort algorithm in expressive way to make it more understandable. Follow comments written above each step/statement in below given merge sort code.

import java.util.*;

public class MergerSort 
{
	public static void main(String[] args) 
	{
		//Unsorted array
		Integer[] a = { 2, 6, 3, 5, 1 };
		
		//Call merge sort
		mergeSort(a);
		
		//Check the output which is sorted array
		System.out.println(Arrays.toString(a));
	}

	@SuppressWarnings("rawtypes") 
	public static Comparable[] mergeSort(Comparable[] list) 
	{
		//If list is empty; no need to do anything
        if (list.length <= 1) {
            return list;
        }
        
        //Split the array in half in two parts
        Comparable[] first = new Comparable[list.length / 2];
        Comparable[] second = new Comparable[list.length - first.length];
        System.arraycopy(list, 0, first, 0, first.length);
        System.arraycopy(list, first.length, second, 0, second.length);
        
        //Sort each half recursively
        mergeSort(first);
        mergeSort(second);
        
        //Merge both halves together, overwriting to original array
        merge(first, second, list);
        return list;
    }
    
	@SuppressWarnings({ "rawtypes", "unchecked" }) 
    private static void merge(Comparable[] first, Comparable[] second, Comparable[] result) 
	{
        //Index Position in first array - starting with first element
        int iFirst = 0;
        
        //Index Position in second array - starting with first element
        int iSecond = 0;
        
        //Index Position in merged array - starting with first position
        int iMerged = 0;
        
        //Compare elements at iFirst and iSecond, 
        //and move smaller element at iMerged
        while (iFirst < first.length && iSecond < second.length) 
        {
            if (first[iFirst].compareTo(second[iSecond]) < 0) 
            {
                result[iMerged] = first[iFirst];
                iFirst++;
            } 
            else 
            {
                result[iMerged] = second[iSecond];
                iSecond++;
            }
            iMerged++;
        }
        //copy remaining elements from both halves - each half will have already sorted elements
        System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
        System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
    }
}
Output:

Input Array :  [ 2, 6, 3, 5, 1, 1, 8 ]
Output Array : [ 1, 1, 2, 3, 5, 6, 8 ]

Input Array :  [ 12, 16, 333, 50, 1000, 5, 897, 1, 3, 66, 13 ]
Output Array : [ 1, 3, 5, 12, 13, 16, 50, 66, 333, 897, 1000 ]

When to use Merge Sort

  1. Merge sort is used when the data structure doesn’t support random access, since it works with pure sequential access (forward iterators, rather than random access iterators). It’s also widely used for external sorting, where random access can be very, very expensive compared to sequential access.

    For example, When sorting a file which doesn’t fit into memory, you might break it into chunks which fit into memory, sort these using independently, writing each out to a file, then merge sort the generated files.

  2. Also, you can use merge sort when you need a stable sort. It’s very important feature of merge sort.
  3. Mergesort is quicker when dealing with linked lists. This is because pointers can easily be changed when merging lists. It only requires one pass (O(n)) through the list.
  4. If there is a lot of parallelization occurs then parallelizing Mergesort is simpler than other sort algorithms.

That’s all about merge sort java tutorial. Drop me your questions/queries in comments section below.

Happy Learning !!

Was this post helpful?

Join 7000+ Awesome Developers

Get the latest updates from industry, awesome resources, blog updates and much more.

* We do not spam !!

14 thoughts on “Merge Sort Java Example”

  1. why use comparable? since Integer implement this interface, if you defines all Comparable array to Integer array, it works well too.

    Reply
  2. Wow this is insanely easy. BTW things weren’t very clear at first. Then I simplified the version and saw how System.arrayCopy works and everything was crystal clear. I’ve added a simplified version of the code which doesn’t involve comparable and Wrapper objects just to make it clear.

    package core.algos.sort;
    
    import java.util.Arrays;
    
    /*
     * <Note on java.lang.System.arraycopy();>
     * 
     * The java.lang.System.arraycopy() method copies an array from the specified
     * source array, beginning at the specified position, to the specified position
     * of the destination array. A subsequence of array components are copied from
     * the source array referenced by src to the destination array referenced by
     * dest.The number of components copied is equal to the length argument.
     * 
     * The components at positions srcPos through srcPos + length - 1 in the source
     * array are copied into positions destPos through destPos + length - 1,
     * respectively, of the destination array.
     * 
     * <Parameters> 
     * src - This is the source array.
     * srcPos - This is the starting position in the source array.
     * dest - This is the destination array.
     * destPos - This is the starting position in the destination data.
     * length - This is the number of array elements to be copied.
     */
    
    /**
     * 
     * In computer science, merge sort (also commonly spelled mergesort) is an
     * O(nlog n) comparison-based sorting algorithm. Most implementations produce a
     * stable sort, which means that the implementation preserves the input order of
     * equal elements in the sorted output. Mergesort is a divide and conquer
     * algorithm. Divide and conquer algorithms divide the original data into
     * smaller sets of data to solve the problem.
     * 
     * During the Mergesort process the object in the collection are divided into
     * two collections. To split a collection, Mergesort will take the middle of the
     * collection and split the collection into its left and its right part. The
     * resulting collections are again recursively splitted via the Mergesort
     * algorithm until they are broke to single element in each collection.
     * 
     * After splitting each collection, mergesort algorithm start combining all
     * collections obtained via above procedure. To combine both collections
     * Mergesort start at each collection at the beginning. It pick the object which
     * is smaller and inserts this object into the 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 create a collection of sorted elements (subset of all elements
     * which needs to be sorted). This process is recursively done for all available
     * collections obtained in first step i.e. splitting the collections.
     * 
     * Once all elements from both collections have been inserted in the new
     * collection, Mergesort has successfully sorted the collection.
     * 
     * <When to use Merge Sort> 
     * 1. Merge sort is used when the data structure doesn’t support random access, 
     * since it works with pure sequential access (forward iterators, rather than 
     * random access iterators). It’s also widely used for external sorting, where 
     * random access can be very, very expensive compared to sequential access. 
     * For example, When sorting a file which doesn’t fit into memory, you might 
     * break it into chunks which fit into memory, sort these chunks independently, 
     * writing each out to a file, then merge sort the generated files.
     * 2. Also, you can use merge sort when you need a stable sort. It’s very important
     * feature of merge sort. 
     * 3. Mergesort is quicker when dealing with linked lists. This is because pointers 
     * can easily be changed when merging lists. It only requires one pass (O(n)) through 
     * the list. 
     * 4. If there is a lot of parallelization occurs then parallelizing Mergesort is 
     * simpler than other sort algorithms.
     * 
     * 
     * <Steps> 
     * 1. Divide the unsorted list into two sublists of about half the size.
     * 2. Sort each of the two sublists. 
     * 3. Merge the two sorted sublists back into one sorted list.
     *
     */
    public class MergeSort {
    	public static void main(String[] args) {
    		// Unsorted array
    		int[] a = { 2, 6, 3, 5, 1, 4 };
    
    		// Call merge sort
    		mergeSort(a);
    
    		// Check the output which is sorted array
    		System.out.println(Arrays.toString(a));
    	}
    
    	/**
    	 * @param list
    	 * @return
    	 */
    	public static int[] mergeSort(int[] list) {
    		// If list is empty; no need to do anything
    		if (list.length <= 1) {
    			return list;
    		}
    
    		// Create 2 lists to hold 1st half and 2nd half of original list.
    		int[] first = new int[list.length / 2];
    		int[] second = new int[list.length - first.length];
    		// Split the array in half and populate above lists.
    		System.arraycopy(list, 0, first, 0, first.length);
    		System.arraycopy(list, first.length, second, 0, second.length);
    
    		// Sort each half recursively
    		mergeSort(first);
    		mergeSort(second);
    
    		// Merge both halves together, overwriting original array
    		merge(first, second, list);
    		return list;
    	}
    
    	/**
    	 * @param first
    	 * @param second
    	 * @param result
    	 */
    	private static void merge(int[] first, int[] second, int[] result) {
    		// Index Position in first array - starting with first element
    		int iFirst = 0;
    
    		// Index Position in second array - starting with first element
    		int iSecond = 0;
    
    		// Index Position in merged array - starting with first position
    		int iMerged = 0;
    
    		// Compare elements at iFirst and iSecond,
    		// and move smaller element at iMerged
    		while (iFirst < first.length && iSecond < second.length) {
    			if (first[iFirst] < second[iSecond]) {
    				result[iMerged] = first[iFirst];
    				iFirst++;
    			} else {
    				result[iMerged] = second[iSecond];
    				iSecond++;
    			}
    			iMerged++;
    		}
    		// copy remaining elements from both halves - each half will have already sorted
    		// elements
    		System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
    		System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
    	}
    }
    
    Reply
  3. I am getting a recursive infinite at line mergeSort(first)
    the code is the same as you have posted what am I missing?

     
       public static void main(String[] args) 
        {
            Integer[] input = { 23, 31, 1, 21, 36, 72, 20, 73, 19}; 
            
            mergeSort(input);
            
            //Check the output which is sorted array
            System.out.println(Arrays.toString(input));
        }
        
        public static Comparable[] mergeSort(Comparable[] list) 
        {
            //Split the array in half in two parts
            Comparable[] first = new Comparable[list.length / 2];
            Comparable[] second = new Comparable[list.length - first.length];
            System.arraycopy(list, 0, first, 0, first.length);
            System.arraycopy(list, first.length, second, 0, second.length);
             
            //Sort each half recursively
            mergeSort(first);
            mergeSort(second);
             
            //Merge both halves together, overwriting to original array
            merge(first, second, list);
            return list;        
            
        }
        
        public static void merge(Comparable[] first, Comparable[] second, Comparable[] result)
        {
            //Index Position in first array - starting with first element
            int iFirst = 0;
             
            //Index Position in second array - starting with first element
            int iSecond = 0;
             
            //Index Position in merged array - starting with first position
            int iMerged = 0;
             
            //Compare elements at iFirst and iSecond, 
            //and move smaller element at iMerged
            while (iFirst < first.length && iSecond < second.length) 
            {
                if (first[iFirst].compareTo(second[iSecond]) < 0) 
                {
                    result[iMerged] = first[iFirst];
                    iFirst++;
                } 
                else
                {
                    result[iMerged] = second[iSecond];
                    iSecond++;
                }
                iMerged++;
            }
            //copy remaining elements from both halves - each half will have already sorted elements
            System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
            System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
        }
    
    Reply
  4. Thanks for you inputs. it clear and easy to understand. but in mergeSort method we are always creating new arrays for first,second these will be created each time in recursion happened. this will more costly(less performance). I think there are other ways to do the sorting without creating the arrays each time by passing the indexes. refer http://www.java2novice.com/java-sorting-algorithms/merge-sort/. but it will be more difficult to understand compared to this Tutorial.

    Reply
    • package com.ds;
      
      import java.util.Arrays;
      
      public class MergeSortUsingIndex {
      
          public static void main(String[] args) 
          {
              //Unsorted array
              int[] arr = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };//{ 2, 6, 3, 5, 1 };//{ 5,4,3,1,2,6};
              
              //Call merge sort
              mergeSort(arr,arr.length);
               
              //Check the output which is sorted array
              System.out.println(Arrays.toString(arr));
             
          }
      	
      	  public static void mergeSort(int[] list,int end) 
      	  {
      		  
      		  if(end<=1)
      			  return;
      
      		  int middle = end/2;
      		  
      		  mergeSort(list,middle);
      
      		  sortUpTo(list,end);
      		  
      	  }
      	  
      	  public static void sortUpTo(int[] list,int end){
      		  
      		  int j=0;
      		  for (int i = 0; i 0){
      				  if(list[j]<list[j-1]){
      					  swap(list,j,j-1);
      				  }
      				  j--;
      			  }
      		  }
      		  
      		}
      	  
           public static void swap(int[] list,int from,int to){
      		  
      		  int temp = list[from];
      		  list[from]=list[to];
      		  list[to] = temp;
           }
      }
      Reply
  5. //copy remaining elements from both halves – each half will have already sorted elements
    System.arraycopy(first, iFirst, result, iMerged, first.length – iFirst);
    System.arraycopy(second, iSecond, result, iMerged, second.length – iSecond);

    while copying you are starting both with index=iMerged, so it will overwrite. no?

    Reply
  6. Thansk for your post, but since result already have the sorted elements in the merge function, why still need these below steps?

    System.arraycopy(first, iFirst, result, iMerged, first.length – iFirst);
    System.arraycopy(second, iSecond, result, iMerged, second.length – iSecond);

    Reply
  7. Hi Lokesh,
    Thanks for all tutorial. They are very helpful.
    Description, diagrammatic explanation of mergesort and code are different.
    It’s bottom up mergesort in diagram and in code it’s top down mergesort in code.

    Reply

Leave a Comment

HowToDoInJava

A blog about Java and related technologies, the best practices, algorithms, and interview questions.