merge_sort.cpp

// Hàm này dùng để trộn 2 phần đã được sắp xếp với nhau
void Merge(int *a, int left, int m, int right)
{
    int l = left, r = m + 1, k = 0;
    int *tmp = new T[right - left + 1];
     
    while(l <= m && r <= right)
    {
        if(a[l] < a[r]) tmp[k++] = a[l++];
        else tmp[k++] = a[r++];
    }
    
    while (l <= m) tmp[k++] = a[l++];
     
    while (r <= right) tmp[k++] = a[r++];
    
    for(int i = 0; i < k; i++)
        a[i+left] = tmp[i];
     
    delete[] tmp;
}
     
// Chia dãy đã cho thành 2 phần cho đến đi không chia được nữa
// Sau khi chia làm 2 phần, sắp xếp từng phần, rồi trộn lại với nhau
void MergeSort(int *a, int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right) / 2;
        MergeSort(a, left, m);
        MergeSort(a, m + 1, right);
        Merge(a, left, m, right);
    }
}