# 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 {
}
}

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)
``````