FOR FREE YEAR SOLVED

The 3-way merge sort is similar to the two way merge sort. The only difference is the array here is divided into three parts till we get all one element arrays.

The procedure of merging will also be similar to that of the merge sort but at a time three array elements are compared and inserted into the final array.

Suppose there are an array of six elements as follows which is to be sorted in ascending order:

The recursion tree for the 3 way merge sort is:

INPUT:
OUTPUT:
PROCESS:
Step 1: [function ‘merge’]
Set i <- low, j <- m1, k <- m2, l <- low
	while i < m1 and j < m2 and k < high repeat
		if arr[i] < arr[j] then 
			if arr[i] < arr[k] then
				Set final[l] <- arr[i]
				Increase l and i by 1
			else
				Set final[l] <- arr[k]
				Increase l and k by 1
			[end of ‘if’]
		else
			if arr[j] < arr[k] then
				Set final[l] <- arr[j]
				Increase l and j by 1 
			else
				Set final[l] <- arr[k]
				Increase l and k by 1  
		[End of ‘if’]
	[End of ‘while’]
	while i < m1 and j < m2 repeat 
		if arr[i] < arr[j] then
			Set final[l] <- arr[i]
			Increase l and i by 1
		else
			Set final[l] <- arr[j]
			Increase l and j by 1
	[End of ‘while’]
	while j < m2 and k < high repeat
		if arr[j] < arr[k] then
			Set final[l] <- arr[j]
			Increase l and j by 1
		else
			Set final[l] <- arr[k]
			Increase l and k by 1
	[End of ‘while’]
	while i < m1 and k < high repeat 
		if arr[i] < arr[k] then 
			Set final[l] <- arr[i]
			Increase l and i by 1 
		else
			Set final[l] <- arr[k]
			Increase l and k by 1
	[End of ‘while’]
	while i < m1 repeat 
		Set final[l] <- arr[i]
		Increase l and i by 1
	[end of ‘while’] 
	while j < m2 repeat 
		Set final[l] <- arr[j]
		Increase l and j by 1
	[End of ‘while’]
	while k < high repeat
		Set final[l] <- arr[k] 
		Increase l and k by 1
	[End of ‘while’]
Step 2: [function sort_recursive]  
	if high - low < 2 then  
		return  
	Set m1<- low + ((high - low) / 3) 
	Set m2 <- low + 2 * ((high - low) / 3) + 1 
	Call ‘sort_recursive’ for index ‘low’ to ‘m1’ 
	Call ‘sort_recursive’ for index ‘m1’ to ‘m2’ 
	Call ‘sort_recursive’ for index ‘m2’ to ‘high’ 
	Call function ‘merge’ to perform 3 way merge sort 
[End of function ‘sort_recursive’]

Step 3: [function ‘sort’] 
	if n = 0 then 
		return 
	for i = 0 to n-1 repeat 
		Set duplicate[i] <- arr[i]
	[End of ‘for’]
	Call the function ‘sort_recursive’ from index o to n 
	for i = 0 to n-1 repeat 
		Set arr[i] <- duplicate[i] 
	[End of ‘for’]
[End of function ‘sort’]
Step 4: [function main]
Read n	
For i=0 to n-1 repeat
		Read arr[i]
	[End of ‘for’]
	For i=0 to n-1 repeat
		Print arr[i]
	[End of ‘for’]
	Call the function ‘sort’ 
	For i=0 to n-1 repeat
		Print arr[i]
[End of function ‘main’]