• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to footer
  • Core Java
  • Design Patterns
  • JSP
  • Servlets
  • Building Tools
  • jQuery
  • Spring
  • Hibernate
  • Mongo DB
  • More
    • HTML
    • SCJP
    • AJAX
    • UML
    • Struts
    • J2EE
    • Testing
    • Angular JS

J2EE Reference

  • Home
  • About Us
    • Java Learning Centers
  • Contact Us

Merge sort algorithm in java

June 19, 2015 By j2eereference Leave a Comment

Merge sort algorithm in java

Merge sort is a neat algorithm, because it’s “the sort that sorts itself”. This means that merge sort requires very few comparisons and swaps; it instead relies on a “divide and conquer” strategy. Merge sort starts by dividing the list to be sorted in half. Then, it divides each of these halves in half. The algorithm repeats until all of these “sub lists” have exactly one element in them. At that point, each 10 sublist is sorted. In the next phase of the algorithm, the sub lists are gradually merged back together (hence the name), until we get our sorted list back.

Example:

  • Divide: Divide the n-element sequence to be sorted into two sub sequences of n/2 elements each
  • Conquer: Sort the sub sequences recursively using merge sort. When the size of the sequences is 1 there is nothing more to do
  • Combine: Merge the two sorted subsequences

 Example of divide:

ms1

 

Conquer and Merge:

 

ms2

 

Java implementation for Merge sort:

Merge sort algorithm consists of two methods: one that “sets up” the algorithm and does the actual work of the algorithm. Second, the primary or “set up” algorithm calls itself recursively.

The primary algorithm looks like this:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void mergeSort(int[] list, int low, int high)
{
if (low < high)
{
// find the midpoint of the current array
int mid = (low + high)/2;
// sort the first half
mergeSort(list,low,mid);
// sort the second half
mergeSort(list,mid+1,high);
// merge the halves
merge(list,low,high);
}
}

This method calculates the midpoint of the array that’s passed in, uses the midpoint to divide the array in half, and then calls mergeSort() for each of these halves. Again, the test is found in the conditional statement, and the stop case occurs when low is greater than or equal to high, which occurs when the size of the array is 1.

mergeSort() will be recursively called until we have arrays of size 1. At that point, the second method, merge(), is called to reassemble the arrays:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public void merge(int[] list, int low, int high)
{
int[] temp = new int[list.length];
// Set the midpoint and the end points for each of the subarrays
int mid = (low + high)/2;
int index1 = 0;
int index2 = low;
int index3 = mid + 1;
// Go through the two subarrays and compare, item by item,
// placing the items in the proper order in the new array
while (index2 <= mid && index3 <= high)
{
if (list[index2] < list[index3])
{
temp[index1] = list[index2];
index1++;
index2++;
}
else
{
temp[index1] = list[index3];
index1++;
index3++;
}
}
// if there are any items left over in the first subarray, add them to
// the new array
while (index2 <= mid)
{
temp[index1] = list[index2];
index1++;
index2++;
}
// if there are any items left over in the second subarray, add them
// to the new array
while (index3 <= high)
{
temp[index1] = list[index3];
index1++;
index3++;
}
// load temp array’s contents back into original array
for (int i=low, j=0; i<=high; i++, j++)
{
list[i] = temp[j];
}
}

Performance of Merge sort algorithm:

  • Since we repeatedly divide our list in half, we expect that the performance of merge sort will have a log2 N term in it.
  • Regardless of best or worst case, the number of swaps in this algorithm is always 2(last-first+1) per merge, where first and last are the indexes of the first and last items in the (sub)list, respectively.
  • In the best case, where the list is sorted, the number of comparisons per pass is (first+last)/2.
  • In the worst case, where the last item of one sublist precedes only the last item of the other sub list, the number of comparisons  is last-first, which approaches N. Thus, for the worst and average cases, the number of comparisons and number of swaps for merge sort is O(NlogN).

Let’s see whether merge sort is stable and in-place or not:

Stability:

Merge sort is stable algorithm

Suppose the array is:5 2 3 5 1
Let’s distinguish the two 5’s as 5(a) and 5(b) .
So our array is:
5(a)  2 3  5(b)  1

ms3
as you can see in the above figure our array is in sorted order and we clearly see that 5(a) comes before 5(b) in initial array and in the sorted array also. So we can clearly see that merge sort is stable.

In place:

An in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes

you can have in-place  version of merge sort and not in-place version of merge sort also.

 

Merge sort’s most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in.

Merge sort also has some demerits. One is its use of 2n locations; the additional n locations are commonly used because merging two sorted sets in place is more complicated and would need more comparisons and move operations.

Related Posts

  • Java Buzzwords
  • Anonymous Inner Class in Java
  • Network Programming – java.net Package
  • Java Regular Expressions
  • Method Local Inner Class in Java
  • URL Processing in Java
  • Difference between Stack and Heap memory
  • What is ThreadMXBean in java?
  • What is serialVersionUID
  • What is exchanger in concurrency?

Filed Under: Core Java

Reader Interactions

Leave a Reply Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Primary Sidebar

FOLLOW US ONLINE

  • View J2eereference-166104970118637’s profile on Facebook
  • View j2eereference’s profile on Twitter
  • View j2eereference’s profile on LinkedIn

Subscribe by email

Recent posts

  • Java Buzzwords
  • Anonymous Inner Class in Java
  • Network Programming – java.net Package
  • Java Regular Expressions
  • Method Local Inner Class in Java
  • URL Processing in Java
  • Iterator Design Pattern Implementation using Java
  • Strategy Design Pattern Implementation using Java
  • Decorator Design Pattern
  • Adapter Design Pattern Implementation using Java
  • JSF Composite Components
  • JSF UI Components
  • What is JavaServer Faces (JSF)?
  • GOF Design Patterns
  • History and Need for Design Patterns

Footer

Core Java
Design Patterns
JSP
Servlets
HTML
Building Tools
AJAX
SCJP
jQuery
Testing
Spring
UML
Struts
Java Centers
Java Training
Home
About Us
Contact Us
Copyright © j2eereference.com. All right reserved.