Answers for "merge sort merge"

Merge sort

class Sort 
{
    void merge(int arr[], int left, int middle, int right)
    {
        int low = middle - left + 1;                    //size of the left subarray
        int high = right - middle;                      //size of the right subarray
 
        int L[] = new int[low];                             //create the left and right subarray
        int R[] = new int[high];

        int i = 0, j = 0;
 
        for (i = 0; i < low; i++)                               //copy elements into left subarray
        {
            L[i] = arr[left + i];
        }
        for (j = 0; j < high; j++)                              //copy elements into right subarray
        {
            R[j] = arr[middle + 1 + j];
        }
        
 
        int k = left;                                           //get starting index for sort
        i = 0;                                             //reset loop variables before performing merge
        j = 0;

        while (i < low && j < high)                     //merge the left and right subarrays
        {
            if (L[i] <= R[j]) 
            {
                arr[k] = L[i];
                i++;
            }
            else 
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        while (i < low)                             //merge the remaining elements from the left subarray
        {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        while (j < high)                           //merge the remaining elements from right subarray
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 

    void mergeSort(int arr[], int left, int right)       //helper function that creates the sub cases for sorting
    {
        int middle;
        if (left < right) {                             //sort only if the left index is lesser than the right index (meaning that sorting is done)
            middle = (left + right) / 2;
 
            mergeSort(arr, left, middle);                    //left subarray
            mergeSort(arr, middle + 1, right);               //right subarray
 
            merge(arr, left, middle, right);                //merge the two subarrays
        }
    }
 
    void display(int arr[])                 //display the array
    {  
        for (int i=0; i<arr.length; ++i) 
        {
            System.out.print(arr[i]+" ");
        } 
    } 

    public static void main(String args[])
    {
        int arr[] = { 9, 3, 1, 5, 13, 12 };
        Sort ob = new Sort();
        ob.mergeSort(arr, 0, arr.length - 1);
        ob.display(arr);
    }
}

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