# 如何实现3路合并排序？代码和算法实现

2021年3月21日17:23:52 发表评论 657 次浏览

## 本文概述

``````Input  : 45, -2, -45, 78, 30, -42, 10, 19 , 73, 93
Output : -45 -42 -2 10 19 30 45 73 78 93

Input  : 23, -19
Output : -19  23``````

## C ++

``````// C++ Program to perform 3 way Merge Sort
#include <bits/stdc++.h>
using namespace std;

/* Merge the sorted ranges [low, mid1), [mid1, mid2)
and [mid2, high) mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge*/
void merge( int gArray[], int low, int mid1, int mid2, int high, int destArray[])
{
int i = low, j = mid1, k = mid2, l = low;

// choose smaller of the smallest in the three ranges
while ((i < mid1) && (j < mid2) && (k < high))
{
if (gArray[i] < gArray[j])
{
if (gArray[i] < gArray[k])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[k++];
}
}
else
{
if (gArray[j] < gArray[k])
{
destArray[l++] = gArray[j++];
}
else
{
destArray[l++] = gArray[k++];
}
}
}

// case where first and second ranges
// have remaining values
while ((i < mid1) && (j < mid2))
{
if (gArray[i] < gArray[j])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[j++];
}
}

// case where second and third ranges
// have remaining values
while ((j < mid2) && (k < high))
{
if (gArray[j] < gArray[k])
{
destArray[l++] = gArray[j++];
}
else
{
destArray[l++] = gArray[k++];
}
}

// case where first and third ranges have
// remaining values
while ((i < mid1) && (k < high))
{
if (gArray[i] < gArray[k])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[k++];
}
}

// copy remaining values from the first range
while (i < mid1)
destArray[l++] = gArray[i++];

// copy remaining values from the second range
while (j < mid2)
destArray[l++] = gArray[j++];

// copy remaining values from the third range
while (k < high)
destArray[l++] = gArray[k++];
}

/* Performing the merge sort algorithm on the
given array of values in the rangeof indices
[low, high). low is minimum index, high is
maximum index (exclusive) */
void mergeSort3WayRec( int gArray[], int low, int high, int destArray[])
{
// If array size is 1 then do nothing
if (high - low < 2)
return ;

// Splitting array into 3 parts
int mid1 = low + ((high - low) / 3);
int mid2 = low + 2 * ((high - low) / 3) + 1;

// Sorting 3 arrays recursively
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, high, gArray);

// Merging the sorted arrays
merge(destArray, low, mid1, mid2, high, gArray);
}

void mergeSort3Way( int gArray[], int n)
{
// if array size is zero return null
if (n == 0)
return ;

// creating duplicate of given array
int fArray[n];

// copying alements of given array into
// duplicate array
for ( int i = 0; i < n; i++)
fArray[i] = gArray[i];

// sort function
mergeSort3WayRec(fArray, 0, n, gArray);

// copy back elements of duplicate array
// to given array
for ( int i = 0; i < n; i++)
gArray[i] = fArray[i];
}

// Driver Code
int main()
{
int data[] = {45, -2, -45, 78, 30, -42, 10, 19, 73, 93};
mergeSort3Way(data, 10);
cout << "After 3 way merge sort: " ;
for ( int i = 0; i < 10; i++)
{
cout << data[i] << " " ;
}
return 0;
}

// This code is contributed by Rashmi Kumari``````

## Java

``````// Java program to perform 3 way Merge Sort
import java.util.*;
public class MergeSort3Way
{
// Function  for 3-way merge sort process
public static void mergeSort3Way(Integer[] gArray)
{
// if array of size is zero returns null
if (gArray == null )
return ;

// creating duplicate of given array
Integer[] fArray = new Integer[gArray.length];

// copying alements of given array into
// duplicate array
for ( int i = 0 ; i < fArray.length; i++)
fArray[i] = gArray[i];

// sort function
mergeSort3WayRec(fArray, 0 , gArray.length, gArray);

// copy back elements of duplicate array
// to given array
for ( int i = 0 ; i < fArray.length; i++)
gArray[i] = fArray[i];
}

/* Performing the merge sort algorithm on the
given array of values in the rangeof indices
[low, high).  low is minimum index, high is
maximum index (exclusive) */
public static void mergeSort3WayRec(Integer[] gArray, int low, int high, Integer[] destArray)
{
// If array size is 1 then do nothing
if (high - low < 2 )
return ;

// Splitting array into 3 parts
int mid1 = low + ((high - low) / 3 );
int mid2 = low + 2 * ((high - low) / 3 ) + 1 ;

// Sorting 3 arrays recursively
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, high, gArray);

// Merging the sorted arrays
merge(destArray, low, mid1, mid2, high, gArray);
}

/* Merge the sorted ranges [low, mid1), [mid1, mid2) and [mid2, high) mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge*/
public static void merge(Integer[] gArray, int low, int mid1, int mid2, int high, Integer[] destArray)
{
int i = low, j = mid1, k = mid2, l = low;

// choose smaller of the smallest in the three ranges
while ((i < mid1) && (j < mid2) && (k < high))
{
if (gArray[i].compareTo(gArray[j]) < 0 )
{
if (gArray[i].compareTo(gArray[k]) < 0 )
destArray[l++] = gArray[i++];

else
destArray[l++] = gArray[k++];
}
else
{
if (gArray[j].compareTo(gArray[k]) < 0 )
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
}

// case where first and second ranges have
// remaining values
while ((i < mid1) && (j < mid2))
{
if (gArray[i].compareTo(gArray[j]) < 0 )
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[j++];
}

// case where second and third ranges have
// remaining values
while ((j < mid2) && (k < high))
{
if (gArray[j].compareTo(gArray[k]) < 0 )
destArray[l++] = gArray[j++];

else
destArray[l++] = gArray[k++];
}

// case where first and third ranges have
// remaining values
while ((i < mid1) && (k < high))
{
if (gArray[i].compareTo(gArray[k]) < 0 )
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}

// copy remaining values from the first range
while (i < mid1)
destArray[l++] = gArray[i++];

// copy remaining values from the second range
while (j < mid2)
destArray[l++] = gArray[j++];

// copy remaining values from the third range
while (k < high)
destArray[l++] = gArray[k++];
}

// Driver function
public static void main(String args[])
{
// test case of values
Integer[] data = new Integer[] { 45 , - 2 , - 45 , 78 , 30 , - 42 , 10 , 19 , 73 , 93 };
mergeSort3Way(data);

System.out.println( "After 3 way merge sort: " );
for ( int i = 0 ; i < data.length; i++)
System.out.print(data[i] + " " );
}
}``````

``````After 3 way merge sort:
-45 -42 -2 10 19 30 45 73 78 93``````

：在进行2路合并排序的情况下, 我们得到以下公式：T(n)= 2T(n / 2)+ O(n)

, 我们得到它的复杂性

O(n对数

3

n)。

。尽管与

2路合并排序

, 由于合并功能中的比较次数会增加, 因此实际花费的时间可能会更长。请参考

3种快速排序