/ * * Merge Sort is sorted by dividing the policy policy implementation, the basic idea is * Sort two sub-set * to 2 subset * will be sorted by dividing the elements to the same size. The subset of subsequences merges to become the desired collection. * /
#include
Using
Namespace
STD;
/ / Define the global array size
INT size = 5;
Void Mergesort
INT A []);
Void MergePass
INT X [],
Int y [],
Int s;
Void Merge
INT C [],
INT D [],
Int L,
Int M,
INT R);
Void Mergesort
Int a []) {
INT * b =
New
Int [size];
INT S = 1;
While (s MergePass (A, B, S); // Merge to array B S = S; MergePass (B, A, S); // Merge to an array a S = S; } Delete [] B; } // ------------------------------------- / / Sort a sequence of sequences adjacent to S // 3 6 4 12 8 5 14 // [3,6] [4,12] [5, 8] [14] // [3, 4, 6, 12] [5, 8, 14] // [3, 4, 5, 6, 8, 12, 14] // // ------------------------------------- Void MergePass INT X [], Int y [], INT S) { // Merger Size of the neighboring number of S INT i = 0; While (i <= (SIZE-2 * S)) { / / The neighboring segment array of merges is S. MERGE (X, Y, I, I S-1, I 2 * S-1); i = i 2 * s; } // The remaining element is less than 2s IF ((i s) MERGE (X, Y, I, I S-1, Size-1); Else // Copy to Y FOR INT j = i; j y [j] = x [j]; Return; } / ************************************************** ************** * How to merge? "Two hands pointed out (already ranked), the smallest information of the left and right piles, * Remove the smaller one of the two will be Point to the one pile shift to the next information. "* Never turn down the information below, just stare at the top two. * (--- http://www.cyut.edu.tw/~ Ckhung / b / al / sort1.shtml) ************************************************** *********************** / Void Merge INT C [], INT D [], Int L, Int M, INT r) { // Merge C [L: M] and C [M 1: R] to D [L: R] INT i = L, j = m 1, k = L; WHILE ((i <= m) && (j <= r))) IF (c [i] <= c [j]) D [k ] = C [i ]; Else D [K ] = C [J ]; IF (i> m) FOR INT Q = J; q <= r; q ) D [K ] = C [q]; Else FOR INT Q = I; Q <= m; Q ) D [K ] = C [q]; } Void Aprint INT B []) { PRINTF "SIZE B:% D / N", Size); FOR INT i = 0; i PRINTF "% d,", b [i]); } } Int main () { INT A [7] = {3, 6, 4, 12, 8, 5, 14}; Size = SizeOf (a) / Sizeof Int); Mergesort (a); Aprint (a); Return 0; }
