Answers for "mergesort merge"

merge sort

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = l+ (r-l)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

merge sort

void merge(int arr[], int l, int m, int r)
    {
         int n=r-l+1,temp[n];
         int i=l,j=m+1,k=0;
         while(i<=m and j<= r)
         {
             if(arr[i]< arr[j]){
                temp[k++] = arr[i++];
             else
                temp[k++] = arr[j++];
         }
         while(i<=m)
            temp[k++] = arr[i++];
         while(j<=r)
            temp[k++] = arr[j++];
         int ind= 0;
         for(int i=l;i<=m;i++)
             arr[i] = temp[ind++];
         for(int j=m+1;j<=r;j++)
            arr[j] = temp[ind++];
    }
    
    void mergeSort(int arr[], int l, int r)
    {
       if(l<r)
       {
           int mid = (r+l)/2;
           mergeSort(arr,l,mid);
           mergeSort(arr,mid+1,r);
           merge(arr,l,mid,r);
       }
    }

merge sort

# Python3 recursive merge sort algorithm -> O(n*log(n))
def merge_sort(A):
    def merge(l, r):
        i = j = 0
        n = []  # merging container
        while i < len(l) or j < len(r):

            # if no more elements to the right,
            # add remaining left elements
            if i == len(l):
                n.extend(r[j:])
                break

            # if no more elements to the left,
            # add remaining right elements
            if j == len(r):
                n.extend(l[i:])
                break

            # if elements left on both sides,
            # add smaller element
            a, b = l[i], r[j]
            if a < b:
                n.append(a)
                i += 1
            else:
                n.append(b)
                j += 1

        return n

    # divide list down to single-elements
    s = len(A)
    if s > 1:
        s //= 2
        l = merge_sort(A[:s])  # split left
        r = merge_sort(A[s:])  # split right
        return merge(l, r)  # merge sides in order
    else:
        return A