Today is January 20, 2021 and is the United States presidential inauguration. Not sure what to expect today or in the following days. Hope all goes well and we can move forward. I believe most of the people in our country are tired of reading and watching political news and propaganda.
Yesterday I attended an ACM webinar “Agent-Human Collaboration and Learning for Improving Human Satisfaction” by Sarit Kraus. She is a professor of computer science at the Bar-Ilan University in Israel.
What called my attention was the concept of having agents for both the automation and the human. I can easily see how that would work in a healthcare or a disaster scenario I do not see how that could work well with autonomous cars. I will go over the slides tomorrow and see if I missed something; otherwise I will send her a message. Hopefully she will have time to respond. Will let you know my findings.
OK, now to the main topic for this post. I am not sure how many software engineers have to implement the merge sort algorithm as part of their work. That does not mean that one should not have a working idea of it. The same holds true for most sorting algorithms which are used quite often at work.
In addition to having a working idea of the algorithm, one must have access to performance data in order to select and test possible algorithms when sorting is required. Some time ago I found the Know Thy Complexities! page which has a couple tables and diagram comparing time and space complexities of different algorithms. I have the page booked marked on Chrome.
Algorithms Time Complexity Space Complexity
Best Average Worst Worst
Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
The motivation for this post was the course Advanced Data Structures and Algorithms in Java 9 by Debasish Ray Chawdhuri on Packt. Part of the code I used to experiment with the algorithm came from his GitHub repository.
There is a good diagram and explanation of the merge sort algorithm in Wikipedia.
The Merge Sort article by GeeksforGeeks also offers several implementations of the algorithm using different programming languages.
The Merge Sort article in Wikipedia contains a nice animation of the merge sort algorithm.
If you perform a search on the web for “merge sort” you should be able to find enough material to spend a couple days reading and experimenting.
main <<< array: [38, 27, 43, 3, 9, 82, 10] mergeSort <<< l: 0 m: 3 r: 6 mergeSort <<< l: 0 m: 1 r: 3 mergeSort <<< l: 0 m: 0 r: 1 merge <<< n1: 1 n2: 1 merge <<< L: [38] merge <<< R: [27] mergeSort <<< l: 2 m: 2 r: 3 merge <<< n1: 1 n2: 1 merge <<< L: [43] merge <<< R: [3] merge <<< n1: 2 n2: 2 merge <<< L: [27, 38] merge <<< R: [3, 43] mergeSort <<< l: 4 m: 5 r: 6 mergeSort <<< l: 4 m: 4 r: 5 merge <<< n1: 1 n2: 1 merge <<< L: [9] merge <<< R: [82] merge <<< n1: 2 n2: 1 merge <<< L: [9, 82] merge <<< R: [10] merge <<< n1: 4 n2: 3 merge <<< L: [3, 27, 38, 43] merge <<< R: [9, 10, 82] main <<< sorted array: [3, 9, 10, 27, 38, 43, 82] main <<< array: [27, 9, 82, 38, 3, 43, 10] main <<< sorted array: [3, 9, 10, 27, 38, 43, 82] main <<< array: [38, 43, 10, 82, 27, 9, 3] main <<< sorted array: [3, 9, 10, 27, 38, 43, 82]
Our test scaffolding uses a single hardcoded array with seven integer elements. We use a first implementation and display some key values. You might wish to try the values used by the Wikipedia animation which could be even more beneficial to understand.
As we can see when the sort operation is over, the values in the entire array end up in ascending order.
We then shuffle the array and run it through two additional implementations. At some point I reused the input array so all passes would use the same initial order. Since we are not performing time comparisons, the order of the values before sorting should not make a difference.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** initial array to sort ****
// Integer[] array = new Integer[]{10, 5, 2, 3, 78, 53, 3, 1, 1, 24, 1, 35,35, 2, 67, 4, 33, 30};
// Integer array[] = new Integer[]{ 12, 11, 13, 5, 6, 7 };
Integer[] array = new Integer[]{38, 27, 43, 3, 9, 82, 10, 1, 72};
// **** display array to sort ****
System.out.println("main <<< array: " + Arrays.toString(array));
// **** 1) merge sort the array ****
mergeSort(array, 0, array.length - 1);
// **** display sorted array ****
System.out.println("main <<< sorted array: " + Arrays.toString(array) + "\n");
// **** shuffle the array ****
List<Integer> lst = Arrays.asList(array);
Collections.shuffle(lst);
array = lst.stream().toArray(Integer[]::new);
// **** display array to sort ****
System.out.println("main <<< array: " + Arrays.toString(array));
// **** auxiliary array ****
Integer[] anotherArray = new Integer[array.length];
// **** 2) merge sort no copy ****
array = mergeSortNoCopy(array, 0, array.length, anotherArray, (a, b) -> a - b);
// **** display sorted array ****
System.out.println("main <<< sorted array: " + Arrays.toString(array) + "\n");
// **** shuffle the array ****
lst = Arrays.asList(array);
Collections.shuffle(lst);
array = lst.stream().toArray(Integer[]::new);
// **** display array to sort ****
System.out.println("main <<< array: " + Arrays.toString(array));
// **** 3) merge sort ****
mergeSort(array, 0, array.length, anotherArray, (a, b) -> a - b);
// **** display sorted array ****
System.out.println("main <<< sorted array: " + Arrays.toString(array));
}
We start with an array of integers in no specific order. We display the array to make sure we start with an unsorted order.
We then sort the elements with the first implementation. The results are displayed. The values appear in sorted order.
The process repeats two more times with two additional implementations.
Note that each time we invoke a sort there is a digit (i.e., 1, 2 or 3). Since the code is split into different functions / methods the numbers are there to help us find the function / method in questions. Your IDE would probably find the proper implementations by just selecting the name and asking. That is the behavior of the VSCode IDE. The same holds for the Eclipse IDE and many others.
Before looking at the code for the different implementations, the idea is to split and sort the array until we end up with one digit in each set / array. We then start selecting the values and moving them to an ordered sort. After the last pass we end up with a sorted array.
This would be a good time to get a piece of paper and pen and try the algorithm. The animation and using the values of the animation in the code would also help. Go for it. I will wait…
…OK, now we can continue.
/**
* MergeSort entry point (1)
* Recursive call.
*/
static void mergeSort(Integer arr[], int l, int r) {
// **** ****
if (l < r) {
// **** find the middle point ****
int m = (l + r) / 2;
// ???? ????
System.out.println("mergeSort <<< l: " + l + " m: " + m + " r: " + r);
// **** sort first and second halves (recursive calls) ****
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// **** merge sorted halves ****
merge(arr, l, m, r);
}
}
We decide if we can continue to split the array. If so we find the midpoint. We then recursively sort the left side of the array followed by the right side.
After recursion returns, we merge the sorted sub arrays.
Note that the implementation makes sense based on the explanations we have read, the diagrams and animations we have looked at.
/**
* Merges two subarrays of arr[] (1).
* First subarray is arr[l..m]
* Second subarray is arr[m + 1 ... r]
*/
static void merge(Integer arr[], int l, int m, int r) {
// **** determine the sizes of two subarrays to be merged ****
int n1 = m - l + 1;
int n2 = r - m;
// ???? ????
System.out.println("merge <<< n1: " + n1 + " n2: " + n2);
// **** create temp arrays ****
Integer L[] = new Integer[n1];
Integer R[] = new Integer[n2];
// **** copy data to the temp arrays ****
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// ???? ????
System.out.println("merge <<< L: " + Arrays.toString(L));
System.out.println("merge <<< R: " + Arrays.toString(R));
// **** initial indexes of first and second subarrays ****
int i = 0, j = 0;
// **** initial index of merged subarry array ****
int k = l;
// **** copy L[] and R[] elements ****
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i++];
}
else {
arr[k] = R[j++];
}
k++;
}
// **** copy remaining elements of L[] (if any) ****
while (i < n1) {
arr[k++] = L[i++];
}
// **** copy remaining elements of R[] (if any) ****
while (j < n2) {
arr[k++] = R[j++];
}
}
This is the merge function / method. We define the indices we will use to traverse the values of interest. We put the sorted values into the arrays and copy back the resulting sorted values into the array.
/**
* Merge sort no copy entry point (2).
*/
public static <E> E[] mergeSortNoCopy(E[] sourceArray, int start, int end, E[] tempArray, Comparator<E> comparator) {
// **** ****
if (start >= end - 1) {
return sourceArray;
}
// **** initialization ****
int mid = (start + end) / 2;
// **** recursive calls ****
E[] sortedPart1 = mergeSortNoCopy(sourceArray, start, mid, tempArray, comparator);
E[] sortedPart2 = mergeSortNoCopy(sourceArray, mid, end, tempArray, comparator);
// **** ****
if (sortedPart2 == sortedPart1) {
if (sortedPart1 == sourceArray) {
merge(sortedPart1, sortedPart2, start, mid, end, tempArray, comparator);
return tempArray;
} else {
merge(sortedPart1, sortedPart2, start, mid, end, sourceArray, comparator);
return sourceArray;
}
} else {
merge(sortedPart1, sortedPart2, start, mid, end, sortedPart2, comparator);
return sortedPart2;
}
}
This function / method implements the second pass of the merge sort algorithm. Note that the previous implementation was restricted to Integers. This implementation supports any data type or class. This can be achieved by passing a comparator.
Also note that we are passing and additional array so we will not need to create additional arrays during the different passes of the merge implementations. That tends to improve the performance of the implementation.
/**
* Merge implementation (2 & 3).
*/
private static <E> void merge(E[] arrayL, E[] arrayR, int start, int mid, int end, E[] targetArray, Comparator<E> comparator) {
// **** ****
int i = start;
int j = mid;
int k = start;
// **** ****
while (k < end) {
// **** ****
if (i == mid) {
targetArray[k] = arrayR[j];
j++;
} else if (j == end) {
targetArray[k] = arrayL[i];
i++;
} else if (comparator.compare(arrayL[i], arrayR[j]) > 0) {
targetArray[k] = arrayR[j];
j++;
} else {
targetArray[k] = arrayL[i];
i++;
}
// **** ****
k++;
}
}
This is the implementation of the merge step. Also note that we will reuse this code in the third implementation.
/**
* Entry call that implements the MergeSort algorithm (3).
*/
public static <E> void mergeSort(E[] sourceArray, int start, int end, E[] tempArray, Comparator<E> comparator) {
// **** end base case ****
if (start >= end - 1) {
return;
}
// **** initialization ****
int mid = (start + end) / 2;
// **** recursive calls ****
mergeSort(sourceArray, start, mid, tempArray, comparator);
mergeSort(sourceArray, mid, end, tempArray, comparator);
// **** merge both arrays ****
merge(sourceArray, start, mid, end, tempArray, comparator);
// **** copy temp to source array ****
System.arraycopy(tempArray, start, sourceArray, start, end - start);
}
This represents the third implementation of the merge sort algorithm. We specify a base case followed by the recursive calls to sort the left and right sides of the array.
After the recursive calls complete we merge the resulting arrays placing the values in sorted order.
/**
* Merge sort entry point (3).
*/
private static <E> void merge(E[] array, int start, int mid, int end, E[] targetArray, Comparator<E> comparator) {
merge(array, array, start, mid, end, targetArray, comparator);
}
This function / method allow us to reuse the merge function / method that we saw in the second implementation of the merge sort algorithm.
Like I said, chances are that in our workplace we might never have the need to implement the merge sort but if we do, I strongly suggest to start with proven code and make the necessary modifications. What is important is to understand the time and space complexities. Note that the worse cases should be taken into account based on the order of the data. Keep in mind that many sorting algorithms tend to perform badly when the data is close or already sorted.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,976 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com