Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
2
Indexable
Never
    public:
    void merge(int arr[], int l, int m, int r)
    {
      // Your code here
         int n1 = m - l + 1, n2 = r - m;
         int *arr1 = new int[n1];
         int *arr2 = new int[n2];
         
         // mảng phụ
         for(int i = 0; i < n1; i++) arr1[i] = arr[l + i];
         for(int i = 0; i < n2; i++) arr2[i] = arr[m + i + 1];
         
         // trộn 2 dãy tăng dần
         int k = l, i = 0, j = 0;
         while(i < n1 && j < n2)
         {
             if(arr1[i] <= arr2[j])
                 arr[k++] = arr1[i++];
             else
                 arr[k++] = arr2[j++];
         }
         
         // sao chép phần còn lại
         while(i < n1) arr[k++] = arr1[i++];
         while(j < n2) arr[k++] = arr2[j++];
         
         delete []arr1;
         delete []arr2;    
    }
    public:
    void mergeSort(int arr[], int l, int r)
    {
        //code here
        if(l < r)
        {
            int m = l + ((r - l)/2);
            mergeSort(arr, l, m);
            mergeSort(arr, m+1 , r);
            merge(arr, l, m, r);
        }
    }