Merge sort on C ++

Another example is an iterative algorithm (it’s also a bottom-up merge sort).

For a change, it is implemented in C in template-style (but g ++ recognizes the code as “its own”). Those. the programmer sets the data type (and if necessary, the comparison function), and the preprocessor generates code for the specified data type.

It may be worthwhile to start with a simple example of the implementation of this algorithm for an int array:

void merge (int a[], int t[], int i, int l, int n) { int j = i + l, n1 = min(j, n), n2 = min(j + l, n), k = i; while (i < n1 && j < n2) t[k++] = a[i] <= a[j] ? a[i++] : a[j++]; while (i < n1) t[k++] = a[i++]; while (j < n2) t[k++] = a[j++]; } void umsort (int a[], int n) { int *t = (int *)malloc(n * sizeof(int)); int l = 1, i; while (l < n) { for (i = 0; i < n; i += 2 * l) merge(a, t, i, l, n); l *= 2; for (i = 0; i < n; i += 2 * l) merge(t, a, i, l, n); l *= 2; } free(t); } 

and only then show it in generalized form.

 // upmergesort_tmpl.h -- bottom-up merge sort in C at template style #ifndef SORT_NAME #error "Must declare SORT_NAME" #endif #ifndef SORT_TYPE #error "Must declare SORT_TYPE" #endif #ifndef SORT_CMP #define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1)) #endif #define SORT_CONCAT(x, y) x ## _ ## y #define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y) #define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x) // делает имя функции наподобие int_mergesort(), // по которому надо вызывать сортировку #define MERGE_SORT SORT_MAKE_STR(mergesort) #define MERGE SORT_MAKE_STR(merge) #ifdef __cplusplus extern "C" { #endif void MERGE_SORT (SORT_TYPE *dst, const size_t size); #ifdef __cplusplus }; #endif #ifndef SORT_NOCODE_GEN #ifndef MIN #define MIN(x,y) ((x) < (y) ? (x) : (y)) #endif /* Слияние 2-х последовательно расположенных в a[], начиная с индекса start уже упорядоченных массивов, размером size элементов. Результат размещается в tmp[] (тоже с индекса start) n -- размер всего сортируемого массива a[] */ static void MERGE (SORT_TYPE a[], SORT_TYPE tmp[], size_t first, size_t size, size_t n) { size_t second = first + size, // начало второго массива end1 = MIN(second, n), // конец первого массива // (дело тут в том, что второго может и не быть...) end2 = MIN(second + size, n), // конец второго массива i = first; // индекс для текущего элемента результата в tmp[] while (first < end1 && second < end2) tmp[i++] = SORT_CMP(a[first], a[second]) <= 0 ? a[first++] : a[second++]; while (first < end1) // остались элементы первого tmp[i++] = a[first++]; while (second < end2) // или второго tmp[i++] = a[second++]; } void MERGE_SORT (SORT_TYPE *dst, const size_t n) { SORT_TYPE *tmp = (typeof(tmp))malloc(n * sizeof(*tmp)); size_t l = 1, // размер уже упорядоченных подмассивов i; // индекс пары последовательных слияющихся подмассивов // начнем слияние с последовательно расположенных подмассивов // из одного элемента while (l < n) { for (i = 0; i < n; i += 2 * l) MERGE(dst, tmp, i, l, n); // теперь уже отсортированные подмассивы вдвое длинее, но они в tmp[] l *= 2; for (i = 0; i < n; i += 2 * l) MERGE(tmp, dst, i, l, n); // а тут их размер опять удвоился и они уже в нужном месте (в a[]) l *= 2; } free(tmp); } #endif // SORT_NOCODE_GEN #undef SORT_CONCAT #undef SORT_MAKE_STR1 #undef SORT_MAKE_STR 

And now how to use it.

Suppose we want to sort the command line arguments, treating them as integers and as double numbers.

For more interest, we will make a separate file (compilation unit) with the double sort function and the real_1000() function, which makes an array of whole arrays of real_1000() values ​​reduced by a factor of 1000 (well, is it necessary to invent something?).

The code for sorting integers (and for the sake of completeness (or to completely blur the brain to the reader?)) And the code for sorting Sishnyh lines will be generated directly into the main.

Then we get tc:

 #include <stdlib.h> #define SORT_TYPE double #define SORT_NAME real #include "upmergesort_tmpl.h" // здесь сгененрили код для void real_mergesort(double *, size_t); #ifdef __cplusplus extern "C" { #endif // даже если компилируем g++, то оставим имя по правилам С, // поскольку в main мы предполагаем, что это C код... double *real_1000(int *, int); #ifdef __cplusplus }; #endif double * real_1000 (int a[], int n) { double *d = (typeof(d))malloc(sizeof(*d) * n); int i; for (i = 0; i < n; i++) d[i] = a[i], d[i] /= 1000; return d; } 

And main (in the file upm_t.c)

 #include <stdio.h> #include <stdlib.h> #include <string.h> #define SORT_TYPE int #define SORT_NAME int #include "upmergesort_tmpl.h" // сгенерили код int_mergesort(int *, size_t); #undef SORT_TYPE #undef SORT_NAME #undef SORT_CMP #define SORT_TYPE char * #define SORT_NAME str #define SORT_CMP strcmp #include "upmergesort_tmpl.h" // сгенерили код str_mergesort(char *, size_t) // и задали strcmp() для сравнения элементов #undef SORT_TYPE #undef SORT_NAME #undef SORT_CMP #define SORT_TYPE double #define SORT_NAME real #define SORT_NOCODE_GEN #include "upmergesort_tmpl.h" // сгенерили прототип real_mergesort(double *, size_t) для компилятора #ifdef __cplusplus extern "C" { #endif // предполагаем, что она м.б. откомпилирована gcc -c double *real_1000(int *, int); #ifdef __cplusplus }; #endif int main (int ac, char *av[]) { int a[ac], n = ac - 1, i; for (i = 1; i < ac; i++) a[i - 1] = atoi(av[i]); int_mergesort(a, n); for (i = 0; i < n; i++) printf("%d\n", a[i]); puts("--- sort all argv[] ---"); str_mergesort(av, ac); for (i = 0; i < ac; i++) printf("%s\n", av[i]); puts("-----"); double *d = real_1000(a, n); real_mergesort(d, n); for (i = 0; i < n; i++) printf("%f\n", d[i]); free(d); return puts("End") == EOF; } 

As a result, we get something like:

 avp@avp-xub11:hashcode$ g++ -c t1.c avp@avp-xub11:hashcode$ g++ upm_t.c t1.o avp@avp-xub11:hashcode$ ./a.out 1 2 3 iii ./bb aaa -2 -7 -7 -2 0 0 0 1 2 3 --- sort all argv[] --- -2 -7 ./a.out ./bb 1 2 3 aaa iii ----- -0.007000 -0.002000 0.000000 0.000000 0.000000 0.001000 0.002000 0.003000 End avp@avp-xub11:hashcode$ 

Everything is OK with gcc too.

Merge sorting is a stable sorting that works for O(n log n) and uses O(n) additional memory.

In C ++, there is already a standard std::inplace_merge algorithm that combines two sorted parts of the same sequence. Using this algorithm, a descending (top-down) merge sort can be written as follows:

 template<typename BidirIterator, typename Compare = std::less<>> void merge_sort(BidirIterator first, BidirIterator last, Compare cmp = {}) { auto n = std::distance(first, last); if (n < 2) return; // Nothing to sort. auto middle = std::next(first, n / 2); merge_sort(first, middle, cmp); merge_sort(middle, last, cmp); std::inplace_merge(first, middle, last, cmp); }