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.

Conceptually, merge sort works as follows in recursive fashion:

- Divide the unsorted list into two sublists of about half the size
- Sort each of the two sublists
- 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

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

- Also, you can use merge sort when you need a stable sort. It’s very important feature of merge sort.
- 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.
- 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 !!**

Saransh Bansal

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.

Lokesh Gupta

Thanks for sharing.

Kevin

I am getting a recursive infinite at line mergeSort(first)

the code is the same as you have posted what am I missing?

dinesh

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.

Mohamed Azeem

Dmitry Sergeevich Kulinich

doesn’t seems to work :)

send

//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?

coco

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);

Lokesh Gupta

I have written explanation in comments.

Ketan

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.

Ketan

Sorry for comment’s got misunderstood initially.