Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị. Nó được xếp vào thể loại sắp xếp so sánh.

Đọc thêm tại: Wikipedia


Code:

#include <iostream>
using namespace std;
void merge_sort(int a[], int n)
{
int i,j,k,low1,up1,low2,up2,size;
int dstam[100];size=1;
while(size<n)
    {
    low1=0;k=0;
    while(low1 +size <n)
        {
        low2=low1+size;
        up1=low2-1;
        if (low2+size-1< n)
            up2=low2+size-1;
        else
            up2=n-1;
        for(i=low1, j=low2; i<=up1 && j<=up2; k++)
            {
            if(a[i]<=a[j])
                dstam[k]=a[i++];
            else
                dstam[k] =a[j++];
            }
        for(;i<=up1;k++)
            dstam[k]=a[i++];
        for(;j<=up2;k++)
            dstam[k]=a[j++];
        low1=up2+1;
        }
    for (i=low1; k<n;i++)
        dstam[k++]=a[i];
    for(i=0;i<n;i++)
        a[i]=dstam[i];
    size*=2;
    }
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    merge_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}