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:
|
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:
|
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
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.
Leave a Reply