Программирование на языке С - Сортировка списков путем слияния

 

2.2.5. Сортировка списков путем слияния

Для получения упорядоченного списка B' последовательность значений В= разделяют на N списков В1=, B2=,...,Bn=, длина каждого из которых 1. Затем осуществляется функция прохода, при которой М>=2 упорядоченных списков B1,B2,...,Bm заменяется на М/2 (или (М+1)/2) упорядоченных списков, B(2i-1)-oго и B(2i)-ого ( 2i<=M ) и добавлением Вm при нечетном М. Проход повторяется до тех пор пока не получится одна последовательность длины N.

Приведем пример сортировки списка путем использования слияния, отделяя последовательности косой чертой, а элементы запятой.

Пример:

     9 / 7 / 18 / 3 / 52 / 4 / 6 / 8 / 5 / 13 / 42 / 30 / 35 / 26;
    7,9 / 3,18 / 4 / 52 / 6 / 8 / 54 / 13 / 30 / 42 / 26 / 35;
    3,7,9,18 /  4,6,8,52 /  5,13,30,42 /  26,35;
    3,4,6,7,8,9,18,52 /   5,13,26,30,35,42;
    3,4,5,6,7,8,9,13,18,26,30,35,42,52.

Количество действий, требуемое для сортировки слиянием, равно Q=N*log2(N), так как за один проход выполняется N сравнений, а всего необходимо осуществить log2(N) проходов. Сортировка слиянием является очень эффективной и часто применяется для больших N, даже при использовании внешней памяти.

Функция smerge упорядочивает массив s сортировкой слиянием, используя описанную ранее функцию merge.

    /* сортировка слиянием */
    double *smerge (double *s, int m, int n)
    { int l,low,up;
      double *merge (double *, int, int, int);
      l=1;
      while(l<=(n-m)) { low="m;" up="m-1;" while (l+up < n) { up="(low+2*l-1" < n) ? (low+2*l-1) : n ; 

merge (s,low,up,l); low="up-1;" } l*="2;" } return(a); } 

Для сортировки массива путем слияния удобно использовать рекурсию. Составим рекурсивную функцию srecmg для сортировки массива либо его части. При каждом вызове сортируемый массив делится на две равных части, каждая из которых сортируется отдельно, а затем происходит их слияние

     /*    рекурсивная   сортировка слиянием  1/2           */
     double *srecmg (double *a, int m, int n)
     { double * merge (double *, int, int, int);
       double * smerge (double *, int, int);
        int i;
       if (n>m)
          { i=(n+m)/2;
            srecmg(a,m,i);
            srecmg(a,i+1,n);
            merge(a,m,n,(n-m)/2+1);
          }
       return (a);
     }