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’]
TIME COMPLEXITY:
As we know from the 2-way merge sort time complexity function:
For more details of 2-way complexity please follow merge sort recursion:
https://mycareerwise.com/programming/category/sorting/merge-sort-using-recursion
Now in the case of 3-way merge sort, we will get a similar type of time function:
If we solve it by master theorem we will get: (Please follow master theorem)
Now here we solve it here by master theorem:
Master Theorem:
And in this case one condition has satisfied that is:
And also p > -1, then [for details please follow the master theorem]
If we put the value of a,b, and p we will get:
SPACE COMPLEXITY:
The space complexity of 3-way merge sort is same as 2-way merge sort: O(n).
Related
Contributed by