If the length of the list is 8, then the index for the mid (middle) element is considered to be 3, which is, the 4th element – index counting begins from 0. So, when the length of the list is even, the index for the mid element is length / 2 – 1.
If the length of the list is 5, then the index for the mid element is considered to be 2, which is the 3rd element. So, when the length of the list is odd, the index for the mid element is length / 2 – 1/2.
It is not difficult to obtain the mid-index of a list with Java! – Just use integer arithmetic. The expression for the mid index is:
So, if the length is 8, the highest index, which is 7, is divided by 2 to give 3 and a 1/2. Integer arithmetic discards the half, leaving you with 3, which is, length / 2 – 1.
If the length is 5, the highest index, which is 4, is divided by 2 to give 2, which is, length / 2 – 1/2.
Merge Sort is a sorting algorithm. In this tutorial, the sorting will result in a final list, from least to highest value. Merge Sort uses the divide and conquer paradigm. The rest of this tutorial explains that, as it applies to Java.
Article Content
- Divide and Conquer for Merge Sort
- The Principal Recursion Method
- The conquer() Method
- Temporary Array for the conquer() Method
- Conclusion
Divide and Conquer for Merge Sort
Divide means to divide the unsorted list into two halves, as explained above. Then divide each of the halves into two more halves. Keep dividing the resulting halves until there are N lists of one element each, where N is the length of the original list.
Conquer means start pairing consecutive lists into one list while sorting the resulting list. The pairing continues until a final sorted list of lengths that is equal to the original length is obtained.
Consider the unsorted list of alphabetic letters:
The length of this list is 7. The following diagram illustrates how merge-sorting of this list is done in theory:
From the diagram, the division to single values takes 3 steps. The conquer, which is merging and sorting, takes another 3 steps to have the sorted final list.
Should a programmer write 6 code segments to achieve this? – No. The programmer needs to have a recursion scheme using a temporary list.
By the way, notice that G looks rather odd in its positioning for division of the first right half. This is because the length of the list is an odd number, 7. If the length were an even number, say 6, Q would have appeared as odd in a similar way for the division of the first left half.
The rest of this article explains “Merge Sort in Java”, using the unsorted list:
The Principal Recursion Method
There are three methods in this program. The methods are, the divide() method, the conquer() method, and the main() method. The divide() method is the principal method. It repeatedly calls itself for the left and right halves and calls the conquer() method at the end of its body. The code for the principal method is:
int mid;
if (beg < end) {
mid = (beg + end)/2;
divide(arr, beg, mid);
divide(arr, mid+1, end);
conquer(arr, beg, mid, end);
}
}
At the start, it takes the array given, the beginning (beg) array index, which is 0, and the ending array index, which is 6. The method will not execute if it does not have at least two elements. The check is done by the if-condition, “if (beg < end)”. The first divide() recall calls the left half of the list, and the second divide() recall calls the right to half of the list.
So, for the first execution or pass, of the divide() method, the if-condition is satisfied (more than one element). The mid index is 3 = (0 + 6) / 2 (integer arithmetic). The three method calls and their order with their arguments become:
divide(arr, 4, 6);
conquer(arr, 0, 3, 6);
There are three calls here. The first of these calls, calls the divide() method again for the left half of the list. The second two methods are noted and reserved in their order, to be executed later. The second divide() call would call the divide() method for the right half of the list. The conquer method would execute the two first halves together.
Before the second pass of the divide() method, the list should be considered divided into two as follows:
In the second pass of the divide() method, the left half of the list is attended to. The call for the second pass is:
This time, the mid index is, 1 = (0 + 3) / 2 (integer arithmetic). The method calls, their order and arguments become,
divide(arr, 2, 3);
conquer(arr, 0, 1, 3);
Note that the new end index is 3, which is the end of the first left half. The first of these calls, calls the divide() method again for the left half of the first left half of the list. The second two methods are noted and reserved in their order, to be executed later, with their new arguments. The second divide() call would call the divide() method for the right half of the first left half of the list. The conquer() method would execute the two new halves.
Before the third pass of the divide() method, the list should be considered divided as follows:
The third pass of the divide method is the call:
In this third pass of the divide() method, the left half of the new sub-list in question is attended to. This time, the mid index is, 0 = (0 + 1) / 2 (integer arithmetic). The method calls, their order and arguments become,
divide(arr, 1, 1);
conquer(arr, 0, 0, 1);
Note that the new end index is 1, which is the end of the new left half. The first of these calls is,
It fails because of the if-condition, “if (beg < end)” – beg, and end are the same, meaning there is only one element. The second divide() method,
Also fails for a similar reason. At this point, the list should be considered divided as,
The third call is:
The conquer call for the two sub-lists is M and K, each consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be K M. The entire list would become:
Remember that there are methods, which were noted and reserved. They would be called in reverse order, now with,
This is the fourth pass of the divide() method. It is to handle the sub-list, Q C, whose beginning index is 2 and ending index is 3. The mid index is now 2 = (2 + 3) / 2 (integer arithmetic). The method calls, their order and arguments become,
divide(arr, 3, 3);
conquer(arr, 2, 2, 3);
The fifth pass of the divide() method is the call,
Note that the beginning and ending index are the same, which means there is only one element. This call fails, because of the if-condition, “if (beg < end)”. The second divide() call,
Also fails for the same reason. At this point, the list should be considered divided as,
The third call in the method pass is:
The conquer call for the two sub-lists is Q and C, each consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be C Q. The entire list would become:
Remember that there are still methods, which were noted and reserved. They would continue to be called in reverse order; now with,
This is the sixth pass of the divide() method. It is to handle the sub-list, E T G, whose beginning index is 4 and ending index is 6. The mid index is now 5 = (4 + 6) / 2 (integer arithmetic). The method calls, their order and arguments become,
divide(arr, 5, 6);
conquer(arr, 4, 5, 6);
The seventh pass of the divide() method is the call,
The second two calls are noted and reserved. Note that the new end index is 5, which is the end of the new left half. The mid index is now 4 = (4 + 5) / 2 (integer arithmetic). The method calls, their order and arguments become,
divide(arr, 5, 5);
conquer(arr, 4, 4, 5);
The eighth pass is:
Note that the beginning and ending index are the same, which means there is only one element. This call fails, because of the if-condition, “if (beg < end)”. The second divide() method call is,
Which also fails for the same reason. At this point, the list should be considered divided as,
The third call is:
It is the conquer call for the two sub-lists: E and T : the first sub-list consisting of one element, and the second sub-list consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be E G . The entire list would become:
Though the E T sequence remains the same, notice that sorting has been taking place, though the final sort is still to come.
Remember that there are still methods that were noted and reserved. They are called in reverse order. They will now be called beginning with,
Note that the new end index is 6, which is the end of the new right half. The mid index is now 5 = (5 + 6) / 2 (integer arithmetic). The method calls, their order and arguments become,
divide(arr, 6, 6);
conquer(arr, 5, 5, 6);
The first two calls fail because they are addressing single element sub-lists. At this point, the entire list is:
The next call is:
It is the conquer call for the two sub-lists: T and G : the first sub-list consisting of one element, and the second sub-list consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be G T . The entire list would become:
Remember that there are still methods that were noted and reserved. They are called in reverse order. The next one to be called is,
It is the conquer call for the two sub-lists: K M and Q C: the first sub-list consisting of two elements, and the second sub-list consisting of two elements. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be C K M Q. The entire list would become:
Another conquer() method that was noted and reserved is:
It is the conquer call for the two sub-lists: E G and T. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be E G T. The entire list would become:
The last conquer() call noted and reserved is:
It is the conquer call for the two sub-lists: C K M Q and E G T: the first sub-list consisting of four elements, and the second sub-list consisting of three elements. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be C E G K M Q T, which is the entire sub-list, that is:
And that ends the merging and sorting.
The conquer() Method
The conquer method merges and sorts two sub-lists. A sub-list consists of at least one value. The conquer method takes as argument, the original array, the beginning index of the first sub-list, the mid index of the two consecutive sub-lists seen together, and the end index of the second sub-list. The conquer method has a temporary array, whose length is that of the original array. The code for the conquer method is:
int i=beg, j=mid+1, k = beg, index = beg;
char temp[] = new char[7];
while(i<=mid && j<=end) {
if(arr[i]<arr[j]) {
temp[index] = arr[i];
i = i+1;
}
else {
temp[index] = arr[j];
j = j+1;
}
index++;
}
if(i>mid) {
while(j<=end) {
temp[index] = arr[j];
index++;
j++;
}
}
else {
while(i<=mid) {
temp[index] = arr[i];
index++;
i++;
}
}
k = beg;
while(k<index) {
arr[k]=temp[k];
k++;
}
}
The main method is:
char arr[] = {'M', 'K', 'Q', 'C', 'E', 'T', 'G'};
TheClass mergeSort = new TheClass();
mergeSort.divide(arr,0,6);
System.out.println("The Sorted Elements:");
for(int i=0;i<7;i++) {
System.out.print(arr[i]); System.out.print(' ');
}
System.out.println();
}
The divide() method, the conquer() method, and the main() method should be combined into one class. The output is:
As expected.
Temporary Array for the conquer() Method
As the sub-list pairs are sorted, the result is held in the temporary array, temp[]. The arrangement of values in the temporary array ultimately replaces the content of the original array. The following shows the arrangement in the original array and that of the temporary array for the different calls of the conquer() method:
arr[7]: M K Q C E T G
temp[7]: K M - - - - -
conquer(arr, 2, 2, 3);
arr[7]: K M Q C E T G
temp[7]: K M C Q - - -
conquer(arr, 4, 4, 5);
arr[7]: K M C Q E T G
temp[7]: K M C Q E T -
conquer(arr, 5, 5, 6);
arr[7]: K M C Q E T G
temp[7]: K M C Q E G T
conquer(arr, 0, 1, 3);
arr[7]: K M C Q E G T
temp[7]: C K M Q E G T
conquer(arr, 4, 5, 6);
arr[7]: C K M Q E G T
temp[7]: C K M Q E G T
conquer(arr, 0, 3, 6);
arr[7]: C K M Q E G T
temp[7]: C E G K M Q T
Conclusion
Merge Sort is a sorting scheme that uses the divide and conquer paradigm. It divides a list of elements into single elements and then starts bringing consecutive pairs of sub-lists together, sorted, beginning from the single element sub-lists. The divide and conquer procedures are together done recursively. This tutorial has explained how it is done in Java.
Chrys
from Linux Hint https://ift.tt/36BJ5MU
0 Comments