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 :

  
public class MergeSort {

    void divideSort(int arr[], int left, int right) { 

        if(left < right) {
		
            int 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. 
        }
    }

    void merge(int arr[], int start, int mid, int end) {

        // Let us take the starting point of left and right array.
	
        int leftStart = start;
        int rightStart = mid+1;
	
        int n = arr.length;
	
        //Create temporary Array of same length as the initial array.
	
        int arrTemp[] = new int[n];
	
        //Copy the contents of the actual array to the temporary array.
	
        for(int i = start ;i <= end ;i++) {
		
            arrTemp[i] = arr[i];
        }
	
        for(int i = start ;i <= end ;i++) {
		
            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++;
            }
        }
    }
	
	
    public static void main(String[] args) {
	
        int arr[] = {7, 4, 8, 1}; 
  
        System.out.println("Array before Sorting"); 
        
        for (int i=0; i<arr.length; ++i) 
            System.out.print(arr[i] + " "); 
            
        System.out.println(); 
  
        MergeSort mergeSort = new MergeSort(); 
        mergeSort.divideSort(arr, 0, arr.length-1); 
        
        System.out.println("Array after Sorting"); 
        
        for (int i=0; i<arr.length; ++i) 
            System.out.print(arr[i] + " "); 
            
        System.out.println(); 
    }
}

In the above code we have two methods:

void divideSort(int arr[], int left, int right)

and

void merge(int arr[], int start, int mid, int end)

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

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

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

	
void divideSort(int arr[], int left, int right) { 

    if(left < right) {
		
        int 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 'void divideSort(int arr[], int left, int right)'.

So, we check if 1st element of l1 i.e. 4 is greater than the 1st element of l2 i.e. 1. And find 4 is greater than 1. So, we take '1' from list l2, and place it in the 1st location of list k.

Now, 'void divideSort(int arr[], int left, int right)' 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,
```
int mid = (left + right) / 2; 
```
And, the variable 'mid' becomes '0'.

So, once again, recursive call is made to 'void divideSort(int arr[], int left, int right)'.
And in step (2), we take the left half of the array(which has one element) and pass it to 'void divideSort(int arr[], int left, int right)'. .

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).
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.
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.
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:

  
void merge(int arr[], int start, int mid, int end) {

    // Let us take the starting point of left and right array.
	
    int leftStart = start;
    int rightStart = mid+1;
	
    int n = arr.length;
	
    //Create temporary Array of same length as the initial array.
	
    int arrTemp[] = new int[n];
	
    //Copy the contents of the actual array to the temporary array.
	
    for(int i = start ;i <= end ;i++) {
		
        arrTemp[i] = arr[i];
    }
	
    for(int i = start ;i <= end ;i++) {
		
        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 'void merge(int arr[], int start, int mid, int end)' 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.

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

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

Next, we create a temporary array,

int arrTemp[] = new int[n];

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

for(int i = start ;i <= end ;i++) {
		
    arrTemp[i] = arr[i];
}

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

for(int i = start ;i <= end ;i++)

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(n log n)
Best Case : O(n log n)
Best Case : O(n log n)

❮❮ PREV NEXT ❯❯