Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А=<6,17,23,39,47> и В=<19,25,38,60> из 5 и 4 элементов дает в качестве результата список С=<6,17,19,23,25,38,39,47,60> из 9 элементов.
Для слияния списков А и В список С сначала полагается пустым, а затем к нему последовательно приписывается первый узел из А или В, оказавшийся меньшим и отсутствующий в С.
Составим функцию для слияния двух упорядоченных, расположенных рядом частей массива s. Параметром этой функции будет исходный массив s с выделенными в нем двумя расположенными рядом упорядоченными подмассивами: первый с индекса low до индекса low+l, второй с индекса low+l+1 до индекса up, где переменные low, l, up указывают месторасположения подмассивов. Функция merge осуществляет слияние этих подмассивов, образуя на их месте упорядоченный массив с индексами от low до up (см. рис.1).
/* слияние списков */
double *merge(double *s, int low, int up, int l)
{
   double *b,*c,v;
   int i,j,k;
   b=calloc(l,sizeof(double));
   c=calloc(up+1-l,sizeof(double));
   for(i=low;i<low+l;i++)
      b[i-low]=s[i];
   for(i=0;i<up-l;i++)
      c[i]=s[i+l+low];
   v=(b[l]=(c[up-l]=(s[low+l-1]>s[up-1]) ?
      (s[low+l-1]+1) : (s[up-1]+1)));
   i=(j=0);
   k=low;
   while(b[i]<v||c[j]<v)
     { if(b[i]<c[j])  s[k]=b[i++];
       else           s[k]=c[j++];
       k++;
     }
   return (s);
}
Рис. 1.  Схема движения индексов при слиянии списков