RUBY - 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 :

def divide_sort(arr, left, right)
	if(left < right)
		mid = ((left + right) / 2).to_i   #Calculates the mid point of the array.
		divide_sort(arr, left, mid)  #Sorts the left half of the array recursively.
		divide_sort(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. 
	end
end		

def merge(arr, start, mid, last)

	# Let us take the starting point of left and right array.
	
	leftStart = start
	rightStart = mid+1
	n = arr.length()
	
	# Create temporary Array of same length as the initial array.
	
	arrTemp = [0]*n
		
	# Copy the contents of the actual array to the temporary array.
	
	for i in start..last
		arrTemp[i] = arr[i]
	end
		
	for	i in start..last
		if (rightStart > last)
			arr[i] = arrTemp[leftStart]
			leftStart+=1
		elsif (leftStart > mid)
			arr[i] = arrTemp[rightStart]
			rightStart+=1
		elsif (arrTemp[leftStart] < arrTemp[rightStart])
			arr[i] = arrTemp[leftStart]
			leftStart+=1
		else
			arr[i] = arrTemp[rightStart]
			rightStart+=1
		end	
	end		
end				
	
	
arr = [7, 4, 8, 1]  
puts "Array before Sorting"
        
for i in 0..arr.length()-1
	puts arr[i]
end	
             
divide_sort(arr, 0, arr.length-1) 
        
puts "Array after Sorting"
 
for i in 0..arr.length()-1
	puts arr[i]
end

Output :

Array before Sorting
7
4
8
1

Array after Sorting
1
4
7
8

In the above code we have two methods :

def divide_sort(arr, left, right)

and

def merge(arr, start, mid, end)

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

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

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

def divide_sort(arr, left, right)
	if(left < right)
		mid = ((left + right) / 2).to_i   #Calculates the mid point of the array.
		divide_sort(arr, left, mid)  #Sorts the left half of the array recursively.
		divide_sort(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.
	end
end

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.

divide_sort(arr, left, mid)

We call the divide_sort(...) method from the divide_sort(...) 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 def divide_sort(arr, left, right).

Now, def divide_sort(arr, left, 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,
```
mid = ((left + right) / 2).to_i
```
And, the variable mid becomes 0.

So, once again, recursive call is made to def divide_sort(arr, left, right).

And in step (2), we take the left half of the array(which has one element) and pass it to def divide_sort(arr, left, right).

In this step, the,
```
if(left < right)
```
condition fails, as both left and right are 0.

So, the recursive call to
```
divide_sort(arr, left, mid)
```
ends.

Now, there is a catch here.

Although, divide_sort(arr, left, mid) called itself(i.e. Recursive call) but the next steps, i.e.
```
divide_sort(arr, mid+1, right)
```
And
```
merge(arr, left, mid, right)
```
Were not executed.

Now, it's time for the execution of divide_sort(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 divide_sort(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 divide_sort(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 `def merge(arr, start, mid, end)` method in detail :

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

def merge(arr, start, mid, last)

	# Let us take the starting point of left and right array.
	
	leftStart = start
	rightStart = mid+1
	n = arr.length()
	
	# Create temporary Array of same length as the initial array.
	
	arrTemp = [0]*n
		
	# Copy the contents of the actual array to the temporary array.
	
	for i in start..last
		arrTemp[i] = arr[i]
	end
		
	for	i in start..last
		if (rightStart > last)
			arr[i] = arrTemp[leftStart]
			leftStart+=1
		elsif (leftStart > mid)
			arr[i] = arrTemp[rightStart]
			rightStart+=1
		elsif (arrTemp[leftStart] < arrTemp[rightStart])
			arr[i] = arrTemp[leftStart]
			leftStart+=1
		else
			arr[i] = arrTemp[rightStart]
			rightStart+=1
		end	
	end		
end

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 def merge(arr, start, mid, 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.

leftStart = start
rightStart = mid+1

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

Next, we create a temporary array as the same length of the actual array,

arrTemp = [0]*n

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

for i in start..last
	arrTemp[i] = arr[i]
end

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

for i in start..last

We will explain the usage of the condition,

if (rightStart > end)

And

elsif (leftStart > mid)

But, at first let us jump to the condition,

elsif (arrTemp[leftStart] < arrTemp[rightStart])
	arr[i] = arrTemp[leftStart]
	leftStart+=1

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+=1
	end

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,

elsif (arrTemp[leftStart] < arrTemp[rightStart]):
	arr[i] = arrTemp[leftStart]
	leftStart+=1

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

elsif (arrTemp[leftStart] < arrTemp[rightStart])
	arr[i] = arrTemp[leftStart]
	leftStart+=1

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,

elsif (leftStart > mid)
	arr[i] = arrTemp[rightStart]
	rightStart+=1

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 ❯❯