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 !!

Leave a Reply

14 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments

About Us

HowToDoInJava provides tutorials and how-to guides on Java and related technologies.

It also shares the best practices, algorithms & solutions, and frequently asked interview questions.

Our Blogs

REST API Tutorial