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

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.

2431

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

24
31

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

24
13

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.

12

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

123

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

1234

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.

17876224131354

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

1787622
4131354

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.

1787
622
413
1354

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,

1787

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

622

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

341

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

1354

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,

617

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

61722

Now since 87 is alone so,

6172287

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,

313

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

31341

Now since 54 is alone so,

3134154

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.

6172287
3134154

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,

36

Compare 17 and 13, since 13 is smallest so,

3613

Compare 17 and 41, since 17 is smallest so,

361317

Compare 22 and 41, since 22 is smallest so,

36131722

Compare 87 and 41, since 41 is smallest so,

3613172241

Compare 87 and 54, since 54 is smallest so,

361317224154

No 87 is left alone,so

36131722415487

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, quicksort is superior to merge sort in terms of space. Quicksort is an in-place sorting algorithm whereas 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’s performance is good while it doesn’t provide stable sorting. Stability is a big deal when sorting arbitrary objects. In the 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 the 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 the case of sorting Objects Merge sort is a better option. That’s why JAVA picked it up for Collections.sort method.

About jkoder