What is Merge sort and usage of Merge sort in JAVA Collections.sort method

Java
What is Merge sort and usage of Merge sort in JAVA Collections.sort method

Manipulating data in a faster and efficient way has always been the fantasy of every language and JAVA is no untouchable in this case. As per JDK-8 Collections.sort method uses Merge sort algorithm for sorting of data in ascending/descending order.

So, what is Merge sort? Well, if you are a library freak you can skip this part and just use Collections library without knowing internal details of it. No harm in it. But if you really want to know its internal working, then bear with me.

The basic funda of Merge sort is “Divide & Conquer”. The large set of problem is divided into smaller subsets of problems, then solving it, and hence merging all the subsets to obtain the original solution.

Let me guide you to the basic principle of Merge sort by using an example, and then we will actually implement this principle to learn Merge sorting in another example.

In this example we have list of integers of size 4 and sort it using merge sort principle in an ascending order.

2 4 3 1

 

Here as per merge sort principle we will break the list into 2 halves.

2 4

 

3 1

And, then sort these 2 lists individually. First one is already sorted, just sort the second one by swapping places.

2 4

 

1 3

Now we have 2 smaller lists in sorted order, and then we merge those 2 smaller lists back together. To do that, we need to compare first items of both lists each. Since, the the lists are already sorted in ascending order, so the the left-most items in the lists are the smallest items in the lists.

So we will compare 2 and 1, and since 1 is smallest so we add 1 back to the main list.

1

Now we compare 2 and 3, and since 2 is smallest so we add 2 back to the main list.

1 2

Now we compare 4 and 3, and since 3 is smallest so we add 3 back to the main list.

1 2 3

And since nothing is left for comparison, so 4 is added back to the main list.

1 2 3 4

And now we have a sorted list of 4 items. That in a nutshell is how Merge sort works, and as promised we will learn to apply merge sort in another example in a detailed manner. Refer below.

In this example we will have a list of 8 items.

17 87 6 22 41 3 13 54

Now as required by Merge sort split the list into 2 halves.

17 87 6 22

 

41 3 13 54

Now we have 2 lists with 4 items each, all in unsorted order. Now we will cut these 2 lists further into 2 halves separately.

17 87

 

6 22

 

41 3

 

13 54

Now we have 4 lists with 2 items each, all in unsorted order. Now we will again recursively cut these 4 lists further into 2 halves separately.

17

 

87

 

6

 

22

 

41

 

3

 

13

 

54

We have 8 lists with 1 item each. Now since each list contains 1 item so we know that each list is now sorted and we just need to merge them back together into 1 list that has 8 items. This is the magic that Merge sort has.

We will start by setting 4 lists with 2 items each. So lets compare the items of first 2 lists i.e. 17 and 87. Since 17 is smallest so,

17 87

Now compare next 2 lists items i.e. 6 and 22. Since 6 is smallest so,

6 22

Now compare next 2 lists items i.e. 3 and 41. Since 3 is smallest so,

3 41

Now compare next 2 lists items i.e. 13 and 54. Since 13 is smallest so,

13 54

So, first stage of merge sort completed. Now, we will merge these 4 lists of 2 items each into 2 lists of 4 items each.

Lets start with first 2 lists that are in sorted order. Now start comparing with left most items of the 2 lists i.e. 17 and 6. Since 6 is smallest so,

6

Now compare 17 and 22. Since 17 is smallest so,

6 17

Now compare 87 and 22. Since 22 is smallest so,

6 17 22

Now since 87 is alone so,

6 17 22 87

Now do comparison for other 2 lists that are in sorted order. Now start comparing with left most items of the 2 lists i.e. 3 and 13. Since 3 is smallest so,

3

Now compare 41 and 13. Since 13 is smallest so,

3 13

Now compare 41 and 54. Since 41 is smallest so,

3 13 41

Now since 54 is alone so,

3 13 41 54

Now we have 2 lists with 4 items each that are in sorted order. And we are just one step away to combine these 2 sorted lists into i sorted list of 8 items.

6 17 22 87

 

3 13 41 54

As usual lets start with left most items of the lists, i.e. 6 and 3, since 3 is smallest so,

3

Compare 6 and 13, since 6 is smallest so,

3 6

Compare 17 and 13, since 13 is smallest so,

3 6 13

Compare 17 and 41, since 17 is smallest so,

3 6 13 17

Compare 22 and 41, since 22 is smallest so,

3 6 13 17 22

Compare 87 and 41, since 41 is smallest so,

3 6 13 17 22 41

Compare 87 and 54, since 54 is smallest so,

3 6 13 17 22 41 54

No 87 is left alone,so

3 6 13 17 22 41 54 87

And, its done! We just used Merge sorting algorithm to sort the 8 items list.

Now as per JDK-8 Arrays.sort uses Quicksort algorithm while Collections.sort uses Merge sort algorithm. However, quick sort is superior than merge sort in terms of space. Quick sort is in-place sorting algorithm where as merge sort is not in-place. In-place sorting means, it does not use additional storage space to perform sorting. In merge sort, to merge the sorted arrays it requires a temporary array and hence it is not in-place. In many scenarios Quicksort performance is good while it doesn’t provide stable sorting. Stability is a big deal when sorting arbitrary objects. In case of sorting primitive values there’s not a difference between Quicksort and Merge sort. For example, suppose you have objects representing email messages, and you sort them first by date, then by sender. You expect them to be sorted by date within each sender, but that will only be true if the sort is stable. That’s why we elected to provide a stable sort (Merge Sort) to sort object references. But in case of sorting Objects Merge sort is better option. That’s why JAVA picked it up for Collections.sort method.

About Anoop Kumar Rai