# c++ - C+ + - 如何打印MergeSort的所有中间步骤？

[14 ,7 ,3 ,12 ,9 ,11 ,6 ,2 ]

[14 ,7 ,3 ,12] [9 ,11 ,6 ,2 ]

[14 ,7] [3 ,12] [9 ,11] [6 ,2 ]

[14] [7] [3] [12] [9] [11] [6] [2 ]

[7 ,14] [3 ,12] [9 ,11] [2 ,6 ]

[3 ,7 ,12 ,14] [2 ,6 ,9 ,11 ]

[2 ,3 ,6 ,7 ,9 ,11 ,12 ,14 ]

``````
/*

Procedure: printMergeSort

Purpose: prints merge sort steps to the console

*/

void printMergeSort(vector <int> left, vector <int> right)

{

for (int i = 0; i < left.size(); ++i)

{

if (i == 0)

printf("[%d,", left[i]);

else if (i < left.size() - 1)

printf("%d,", left[i]);

else

printf("%d],", left[i]);

}

for (int i = 0; i < right.size(); ++i)

{

if (i == 0)

printf("[%d,", right[i]);

else if (i < right.size() - 1)

printf("%d,", right[i]);

else

printf("%d] n", right[i]);

}

}``

``````

``````
/*

Procedure: merge

Purpose: Helper funcrion for mergeSort...

Sorts the subarrays and merges them

*/

void merge(vector<int>& leftVector, vector<int>& rightVector, vector<int>& vectortoMerge)

{

int lefttmostValue = leftVector.size();

int rightmostValue = rightVector.size();

int i = 0, j = 0, k = 0;

//printMergeSort(leftVector, rightVector);

while (j < lefttmostValue and k < rightmostValue)

{

if (leftVector[j] < rightVector[k])

{

vectortoMerge[i] = leftVector[j];

//printf("%d", vectortoMerge[i]);

++j;

}

else

{

vectortoMerge[i] = rightVector[k];

//printf("%d", vectortoMerge[i]);

++k;

}

++i;

}

while (j < lefttmostValue)

{

vectortoMerge[i] = leftVector[j];

//printf("%d", vectortoMerge[i]);

++j; ++i;

}

while (k < rightmostValue)

{

vectortoMerge[i] = rightVector[k];

//printf("%d", vectortoMerge[i]);

++k; ++i;

}

}

/*

procedure: mergeSort

Purpose: Main function for the merge sort algorithm....

Splits the vector into 2 and makes a call the merge() function

*/

void mergeSort(vector<int>& vectortoSort)

{

if (vectortoSort.size() <= 1) return;

int middleElement = vectortoSort.size() / 2;

vector<int> leftVector;

vector<int> rightVector;

for (int j = 0; j < middleElement; ++j)

leftVector.push_back(vectortoSort[j]);

for (int j = 0; j < (vectortoSort.size()) - middleElement; ++j)

rightVector.push_back(vectortoSort[middleElement + j]);

printMergeSort(leftVector, rightVector);

printf(",");

mergeSort(leftVector);

mergeSort(rightVector);

merge(leftVector, rightVector, vectortoSort);

}

``````

[14 ,7 ,3 ,12]，[9 ,11 ,6 ,2] [14 ,7]，[3 ,12] [14 ,[7 ,[3 ,[12 ,[9 ,11]，[6 ,2] [9，[11，[6，[2，

``````
printf("[");

for (int i = 0; i < left.size(); ++i)

{

if (i != 0)

printf(",");

printf("%d", left[i]);

}

printf("], [");

for (int i = 0; i < right.size(); ++i)

{

if (i != 0)

printf(",");

printf("%d", right[i]);

}

printf("]n");

``````