Merge sort algorithm in java

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:

 

Conquer and Merge:

 

 

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:

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:

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

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.