Сортировка слиянием

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй».

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

Реализация на JAVA

public class MergeSort {
     public static void mergesort (int[] a) {
          mergesort(a, 0, a.length-1);
   }

     private static void mergesort (int[] a, int l, int r) {
          //base case: a[l..r] is empty or has only one element
          if ( l>=r ) return;

          //recursion step: a[l..r] is not empty
          //divide into sublists and merge
          int m = (l+r)/2;
          mergesort (a, l, m);
          mergesort (a, m+1, r);
          merge (a, l, m, r);
     }

     //merges to sublists
     private static void merge (int[] a, int l, int m, int r) {
          //base case: second sublist is empty
          if (m+1>r) return;

          int[] b = new int[a.length];
          //create temporary array //copy a[l..m] to b[l..m]
          for (int i=l; i!=m+1; i++) {
               b[i] = a[i];
          }
          //copy a[m+1..r] to b[m+1..r] in reverse order
          for (int i=m+1; i!=r+1; i++) {
               b[i] = a[r+m+1-i];
          }
//merge b[l..m] with b[m+1..r] to a[l..r]
          int k=l; int j=r; //pointer wandering from outside inward
          for (int i=l; i!=r+1; i++) {
               if (b[k] <= b[j]) a[i] = b[k++]; else a[i] = b[j--];
          }
     }
}

Реализация на C

/* Merge sort 
// The merge sort divides the array into two sub-arrays, sorts them and then
// calls merge to merge the two arrays back together.
*/
void Merge( int a[], int b[], int c[], int m, int n )
{
 int i = 0, j = 0, k = 0;
 while (i < m && j < n)
 {
 if( a[i] < b[j] )
 {
 c[k++] = a[i++];
 }
 else
 {
 c[k++] = b[j++];
 }
 }

 while ( i < m )
 {
 c[k++] = a[i++];
 }

 while ( j < n )
 {
 c[k++] = b[j++];
 }
}

void merge_sort( int key[], int n )
{
 int j, k, m, *w;
 for( m = 1; m < n; m *= 2 );
 if (m != n)
 {
 printf ("ERROR: Size of the array is not power of 2.");
 }
 else
 {
 w = calloc( n, sizeof(int) );
 for( k = 1; k < n; k *= 2 )
 {
 for( j = 0; j < (n - k); j += 2 * k )
 {
 Merge(key + j, key + j + k, w + j, k, k);
 for ( j = 0; j < n; j++) key[j] = w[j];
 }
 }
 free(w);
 }
}

Реализация на C++

/* Sorts first n elements of array a[] in non-decreasing order. */
template<typename T> void merge_sort(T a[], int n)
{
 int i, j, k;
 T tmp;

 /* For small arrays, insertion sort is much faster */
 if (n < 64) {
 for (i = 1; i < n; i++) {
 tmp = a[i];
 for (j = i-1; j >= 0 && tmp < a[j]; j--) a[j+1] = a[j];
 a[j+1] = tmp;
 }
 return;
 }

 int f = n / 2; /* f = number of elements in first half */

 /* Recursively sort both halves */
 merge_sort(a, f);
 merge_sort(a+f, n-f);

 /* Merge */
 T *s = new T[n]; /* temporary array to keep the sorted sequence */

 for (i = 0, j = f, k = 0; i < f && j < n;)
 s[k++] = (a[i] < a[j]) ? a[i++] : a[j++];

 while (i < f) s[k++] = a[i++];
 while (j < n) s[k++] = a[j++];

 for (i = 0; i < n; i++) a[i] = s[i];
 delete[] s;
}

/* Example of usage: */
#include <cstdio>
#include <cstdlib>
int main()
{
 int n=100, *a=new int[n];
 for (int i = 0; i < n; i++) a[i] = rand();
 merge_sort(a, n);
 for (int i = 0; i < n; i++) printf("%d\n", a[i]);
}

Литература

Ананий В. Левитин Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 169-172. ISBN 0-201-74395-7
Википедия


Алгоритмы сортировок и их реализации
	Главная