KOTLIN - MERGE SORT CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

So, we will start the coding by comparing the above nine step process. The coding for Merge sort is based on a technique called Recursion. If you are not aware of Recursion you can read it. However, in this tutorial, we will try to explain Recursion as much as possible.

Example :

class MergeSort {

    fun divideSort(arr: Array<Int>, left: Int, right: Int) {

        if (left < right) {

            var mid = (left + right) / 2; // Calculates the mid point of the array.
            divideSort(arr, left, mid);  // Sorts the left half of the array recursively.
            divideSort(arr, mid + 1, right); // Sorts the second part of the array recursively.

            merge(arr, left, mid, right); // Merge or combine the both parts of array.
        }
    }

    fun merge(arr: Array<Int>, start: Int, mid: Int, end: Int) {

        // Let us take the starting point of left and right array.

        var leftStart = start;
        var rightStart = mid + 1;

        var n = arr.size;

        //Create temporary Array of same length as the initial array.

        var arrTemp = Array(n) { 0 }

        //Copy the contents of the actual array to the temporary array.

        for (i in start..end) {

            arrTemp[i] = arr[i];
        }

        for (i in start..end) {

            if (rightStart > end) {

                arr[i] = arrTemp[leftStart];
                leftStart++;
            } else if (leftStart > mid) {

                arr[i] = arrTemp[rightStart];
                rightStart++;
            } else if (arrTemp[leftStart] < arrTemp[rightStart]) {

                arr[i] = arrTemp[leftStart];
                leftStart++;
            } else {

                arr[i] = arrTemp[rightStart];
                rightStart++;
            }
        }
    }
}

fun main(args: Array<String>) {

    var arr = arrayOf(7, 4, 8, 1);

    println("Array before Sorting");

    for (i in 0..(arr.size - 1))
        print("${arr[i]}, ");

    println();

    var mergeSort = MergeSort();
    mergeSort.divideSort(arr, 0, arr.size - 1);

    println("Array after Sorting");

    for (i in 0..(arr.size - 1))
        print("${arr[i]}, ");

    println();
}

Output :

Array before Sorting
7, 4, 8, 1,
Array after Sorting
1, 4, 7, 8,

In the above code we have two methods:

fun divideSort(arr: Array<Int>, left: Int, right: Int)

and

fun merge(arr: Array<Int>, start: Int, mid: Int, end: Int)

The first method fun divideSort(...) divides the list into two parts and then sorts them individually.

And the next method fun merge(...) merges the splited lists after sorting them.

Let us understand the divideSort(...) method in detail:

fun divideSort(arr: Array<Int>, left: Int, right: Int) {

	if (left < right) {

		var mid = (left + right) / 2; // Calculates the mid point of the array.
		divideSort(arr, left, mid);  // Sorts the left half of the array recursively.
		divideSort(arr, mid + 1, right); // Sorts the second part of the array recursively.

		merge(arr, left, mid, right); // Merge or combine the both parts of array.
	}
}

So, we are passing the array arr, its starting point i.e. 0(mentioned left) and the end point i.e. arr.length-1 (mentioned right).

The array contains (1, 4, 7, 8). And the left is 0. The length of the array is 4. Which means (4-1), i.e. 3. So, the right is 3.

In the next step we check

if(left < right)

Which means the array length should be more than 1.

Then we calculate the mid point of the array, so that we can divide the array into two parts.

Now, comes the fun part.

divideSort(arr, left, mid);

We call the divideSort(...) method from the divideSort(...) method. And this is called recursion. Where a method keeps on calling itself until it comes to an end. And it maintains an internal stack which is hidden from the programmer.

Let us see it in brief,

So, in step (1), we take the left half of the array(i.e. left is 0 and mid is 1) and pass it to fun divideSort(arr: Array<Int>, left: Int, right: Int).

Now, fun divideSort(arr: Array<Int>, left: Int, right: Int) method has the array arr that contains (7, 4). Where the left is 0 and the right is 1.

Then we check,

if(left < right)

And the condition satisfies, as 0 is less than 1.

Next, we calculate the midpoint,

var mid = (left + right) / 2;

And, the variable mid becomes 0.

So, once again, recursive call is made to fun divideSort(arr: Array<Int>, left: Int, right: Int).

2. And in step (2), we take the left half of the array(which has one element) and pass it to fun divideSort(arr: Array<Int>, left: Int, right: Int).

In this step, the,

if(left < right)

condition fails, as both left and right are 0.

So, the recursive call to

divideSort(arr, left, mid);

ends.

Now, there is a catch here.

Although, divideSort(arr, left, mid) called itself(i.e. Recursive call) but the next steps, i.e.

divideSort(arr, mid+1, right);

And

merge(arr, left, mid, right);

Were not executed.

Now, it's time for the execution of divideSort(arr, mid+1, right) and merge(arr, left, mid, right). And it starts moving backwards(We will explain it below).

3. In step (3), the recursive call starts for divideSort(arr, mid+1, right). And, guess what values we are going to take? The values from step (1).

i.e.

And why is that ? It is because, the right half (i.e. 4) was never dealt with. And the compiler makes a wise decision by taking that.

Similarly, there is one element for this call.

And this step comes to an end because

if(left < right)

condition fails.

4. In step (4), the merge(arr, left, mid, right) method is called and it merges two halfs after sorting them.

Note : We will explain the merge(...) method below.

Once the merge(...) method is executed successfully. The compiler goes back to the main array. As it knows the calculation for the right half was never done.

5. In step (5), the right half of the array is taken and compiler calls divideSort(arr, mid+1, right);. Where the array arr contains (8,1) and mid+1 is 2 and right is 3.

And all the steps are repeated till step 9 until all the values are sorted.

Explanation of 'merge(...)' method in detail:

The merge(...) method has the following lines of code:

fun merge(arr: Array<Int>, start: Int, mid: Int, end: Int) {

	// Let us take the starting point of left and right array.

	var leftStart = start;
	var rightStart = mid + 1;

	var n = arr.size;

	//Create temporary Array of same length as the initial array.

	var arrTemp = Array(n) { 0 }

	//Copy the contents of the actual array to the temporary array.

	for (i in start..end) {

		arrTemp[i] = arr[i];
	}

	for (i in start..end) {

		if (rightStart > end) {

			arr[i] = arrTemp[leftStart];
			leftStart++;
		} else if (leftStart > mid) {

			arr[i] = arrTemp[rightStart];
			rightStart++;
		} else if (arrTemp[leftStart] < arrTemp[rightStart]) {

			arr[i] = arrTemp[leftStart];
			leftStart++;
		} else {

			arr[i] = arrTemp[rightStart];
			rightStart++;
		}
	}
}

As we know merging is a process where we combine two sorted arrays/lists after sorting them.

Let us take the lists from step 4 and step 8 and see how they are merged after sorting.

Seeing the above diagram, in fun merge(arr: Array<Int>, start: Int, mid: Int, end: Int) method, we pass the array, arr that contains the values (4,7,1,8). Where start is 0, mid is 1 and end is 3. We have assumed that (4,7) is the left half and (1,8) is the right half.

Now, we have to combine them using the above method.

Initially, we have taken the starting point of the left and right arrays.

	var leftStart = start;
	var rightStart = mid+1;

Which means, leftStart = 0 and rightStart = mid + 1, which is, rightStart = 2.

Next, we create a temporary array,

var arrTemp = Array(n) { 0 }

And copy the contents of the actual array arr[] to the temporary array arrTemp[].

for (i in start..end) {
	arrTemp[i] = arr[i];
}

Then we run a loop, inside which the actual merge happens after sorting.

	for (i in start..end)

We will explain the usage of the condition,

if (rightStart > end)

And

else if (leftStart > mid)

But, at first let us jump to the condition,

else if(arrTemp[leftStart] < arrTemp[rightStart]) {

	arr[i] = arrTemp[leftStart];
	leftStart++;
}

As we have seen, leftStart = 0 and rightStart = 2.

So, the above condition doesn't match as arrTemp[leftStart] i.e. 4 is greater than arrTemp[rightStart] i.e. 1.

And we jump to the else condition,

else {

	arr[i] = arrTemp[rightStart];
	rightStart++;
}

And arr[0] is initialized with the value from arrTemp[2] i.e. 1. Also we increment rightStart by 1. So, rightStart is 3 now.

Again, we check with the if conditions and finally reach the condition,

else if(arrTemp[leftStart] < arrTemp[rightStart]) {

	arr[i] = arrTemp[leftStart];
	leftStart++;
}

And, arrTemp[leftStart] is arrTemp[0] and arrTemp[rightStart] is arrTemp[3] as rightStart is 3.

Which means 4 is less than 8. So, we initialise arr[1] with arrTemp[leftStart] i.e. 4. And leftStart is incremented by 1. i.e. leftStart is 1 now.

Once again, after all the if conditions, we come to the condition

else if(arrTemp[leftStart] < arrTemp[rightStart]) {

	arr[i] = arrTemp[leftStart];
	leftStart++;
}

And, arrTemp[leftStart] is arrTemp[1] as leftStart is 1 and arrTemp[rightStart] is arrTemp[3] as rightStart is 3.

Which means 7 is less than 8. So, we initialise arr[2] with arrTemp[leftStart] i.e. 7. And leftStart is incremented by 1. i.e. leftStart is 2 now.

Note : The value of leftStart is 2 currently. Which shouldn't be, as the location 2 and 3 belongs to the right array. And so we have the if condition if (rightStart > end) and else if (leftStart > mid) to deal with the situations when the position of left array reaches the right array or the right array crosses the end of array.

So, the condition,

else if (leftStart > mid) {

	arr[i] = arrTemp[rightStart];
	rightStart++;
}

matches and arr[3] is assigned with the value 3 from arrTemp[rightStart] i.e. arrTemp[3].

And we come to the end of the for loop and find the elements are sorted.

Efficiency / Running time of Merge Sort

There are complicated processes to understand the efficiency/running for Merge Sort. But we will keep it simple, so that it becomes simple to understand and we can calculate the running time for any algorithm this way.

Let us look at the entire process to calculate the Running time:

At first we keep on dividing the list by calculating the mid point.

And the above step only takes constant time or O(1) because we are just dividing the array by calculating the mid point.

Then we will sort each divided arrays and then merge them after sorting. Let us see the below diagram and understand it,

At the top level we have divided the list into 4 parts. Although, they contain single elements. Still we can assume that we will sort each element. Then in the merge/combine step, we group them as two elements and sort them. So, combine/merge step will run 4 times

Next, the lists are divided into two parts. So, we can assume we have to sort 2 lists individually. And the combine/merge step will run 4 times because it will compare each element in both arrays.

And finally we have the main array which is one.

To understand it better, let us take an array of size 8.

So, at first we divide the array that will take constant time.

Then we will sort each divided arrays and then merge them after sorting. Let us see the below diagram and understand it,

Now, if we consider the above diagram. Although, the merge/combining happens 8 times in each level. But the parts on which it does the merge/combining comes down in the order 8, 4, 2, 1. Which has 4 levels. And the other way to represent this order is log 8.

Note : The above levels are - 8, 4, 2, 1 - It has 4 levels or log 8 = 3 + 1. In other words log n + 1. If we neglect 1, we are left with log n.

We know that the size of the list is 8 or n. So, the time taken by merge/combine step is n. And the time taken to combine each part is log n.

So, if we consider the total running time. It becomes O(nlog n).

And since, it compares by dividing the list. The running time in,

Best Case : O(nlogn)

Average Case : O(nlogn)

Worst Case : O(nlogn)

❮❮ PREV NEXT ❯❯