# K-path merging of (C/C++)k ordered arrays for complexity O(nlogk)

Suppose there are k ordered arrays, each of which contains n elements. Your task is to merge them into a single ordered array, which has kn elements in total.
Design and implement an effective divide and conquer algorithm to solve the k-path merge operation problem, and analyze the time complexity.

## thinking

Divide and conquer algorithm is to merge two ordered arrays
The relevant merge code comes from the java code written by the blogger on the Internet. The length of the java array can be calculated directly, but it is troublesome for the C + + array to pass in the length manually So it took some time to rewrite it into C + +

``````#include <iostream>
#define N 5
#define INDEX_COUNT 5
using namespace std;
int INDEX[INDEX_COUNT][N] =
{ 1,4,5,8,9,
2,6,8,9,10,
3,5,5,7,8,
4,5,6,7,12,
1,5,8,9,10 };

int MERGED_INDEXS[N*INDEX_COUNT];

void showArray(int a[], int length)
{
for (int i = 0; i < length; i++)
{
cout << a[i] << " ";
}
cout << "\n";
}

int* mergeTwoArrays(int* A, int* B,int lengthA,int lengthB) {
int* temp = new int[lengthA + lengthB];
int index = 0, i = 0, j = 0;
while (i < lengthA && j < lengthB) {
if (A[i] < B[j]) {
temp[index++] = A[i++];
}
else {
temp[index++] = B[j++];
}
}
while (i < lengthA) {
temp[index++] = A[i++];
}
while (j < lengthB) {
temp[index++] = B[j++];
}
return temp;
}

// The depth of divide and conquer recursion is O(log k), and the time complexity of each layer is O(n)
int* kMergeSort(int arrays[INDEX_COUNT][N], int start, int end) {
if (start >= end) {
return arrays[start];
}
int mid = start + (end - start) / 2;
int* left = kMergeSort(arrays, start, mid);
int* right = kMergeSort(arrays, mid + 1, end);
cout << "Merge INDEX" << start << "and INDEX" << end<<endl;
return mergeTwoArrays(left, right, N*(mid - start + 1), N*(end - mid));
}

int* mergekSortedArrays(int arrays[INDEX_COUNT][N],int length) {
int* list = new int[N*INDEX_COUNT];
if (arrays == NULL) {
return list;
}
int* ans = kMergeSort(arrays, 0, length - 1);
showArray(ans, N*INDEX_COUNT);
return list;
}

int main(void) {
for (int i = 0; i < INDEX_COUNT; i++) {
cout << "array" << i << ":";
showArray(INDEX[i], N);
}
mergekSortedArrays(INDEX, INDEX_COUNT);
//showArray(mergeTwoArrays(INDEX, INDEX, N, N), N + N);
system("pause");
return 0;
}
``````

Keywords: Java

Added by Calamity-Clare on Fri, 06 Dec 2019 02:42:13 +0200