Merge Sort

Merge Sort is based on divide & conquer approach, first we divide array into two parts until we got single element then merge the single single element and create a subarray, Now merge two sorted subarray into single array likewise in final we got the final sorted array.
In Conquer approach we have i, j k where i if left subarray, j is right subarray now we are comparing elements right with left & add it to tempArray. k index is used to fill on temp array
Time Complexity:- O(n log(n))
Space Complexity:- O(n)

// Merge Sort...
func mergeSort(_ arr: inout [Int], _ l: Int, _ r: Int) {
    //print("MS called with ", l,r)
    if (l < r) {
        let mid = (l + r) / 2;
        mergeSort(&arr, l, mid); // left half // Divide
        mergeSort(&arr, mid + 1, r); // right half // Divide
        mergeSortConquer(&arr, l, mid, r); // merging sorted halves// Conquer
    } else {
       // print("Discarded--> ", l,r)
    }
}

func mergeSortConquer(_ arr: inout [Int],  _ lowerBound: Int,  _ mid: Int,  _ upperBound: Int) {
    var i = lowerBound; // starting index of left half of array
    var j = mid + 1; // starting index of right half of array
    var k = lowerBound; // k is index used to transfer elements in temp array
    var tempArray: [Int] = Array.init(repeating: 0, count: arr.count) // temp array
   // print(lowerBound, upperBound, "entered here for sorting INDEX -->", i, j, upperBound, " -- Respective Values-->", arr[i], arr[j])
   // print("entered with", lowerBound ,mid, upperBound)
    // storing elements in the temp array in a sorted manner//
    
    while i <= mid && j <= upperBound {
        if (arr[i] < arr[j]) {
            tempArray[k] = arr[i];
            i+=1;
        } else {
            tempArray[k] = arr[j];
            j+=1;
        }
        k+=1;
    }
    // Note:- In below code we are transferring the element from any two subarray 
    // if elements on the left half are still available to insert //
    
    if i > mid {
        while j <= upperBound {
            //print("Left entered in if loop...", arr[j])
            tempArray[k] = arr[j];
            k+=1;
            j+=1;
        }
    } else {
        // if elements on the right half are still available to insert  //
        while i <= mid {
            // print("Right entered in if loop...", arr[i])
            tempArray[k] = arr[i];
            k+=1;
            i+=1;
        }
    }
    // transferring all elements from temporary to arr //
    for k in lowerBound...upperBound {
        arr[k] = tempArray[k];
    }
//    print("tempArray---------", tempArray)
}

var arr = [8, 7, 6, 5]
mergeSort(&arr, 0, arr.count - 1)
print("merge Sort-->", arr)