 # Merge Sort Algorithm

Hi there i was learning about merge sort algorithm and i tried to found the logic in deep, adapting it to javascript, i realized it is a quite diferent. i would like to explain here the logic i founded in the algorithm using recursive way and please let me know if it is correct…

i have an array => [73,90,5,7,2,3,12,1,0]

``````function mergeSort(arr){
if(arr.length == 1){
return arr
}else{
let middle = Math.floor(arr.length / 2)
let left = arr.slice(0,middle)
left right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}

}
function merge(left, right){
let indexLeft = 0;
let indexRight = 0;
let result =[]
while(indexLeft < left.length &&  indexRight < right.length){
if(left[indexLeft < right[indexRight]){
result.push(left[indexLeft])
indexLeft ++
}else{
result.push(right[indexRight])
indexRight ++
}
}
return result.concat(left.slice(indexLeft), right.slice(indexRight))
}

``````

Here the logic how i think it works.

mergeSort it wil beign executing it self til arr.length == 1;

array = [73,90,5,7,2,3,12,1,0]
L R
[73,90,5,7], [2,3,12,1,0]
L R
L R [2,3]<=>[12,1,0]
L R L R
[73,90]<=>[5,7] <=><=><=>[1,0]

``````				    L      R
<=>
``````

L R L R
<=>  <=>  <=> 

then merge will execute

merge(left=73, right=90)
result=[]
left < right
73 < 90 => True
indexLeft++

result = [73,73,90]=>remove indexLeft
result = [73,90]
merge(left=5, right=7)
result = []
left < right
5 < 7=>true
indexLeft ++
result =[5,5,7]=>remove indexLeft
result = [5,7]

merge(left=[73,90], right=[5,7])
result = []
left < right
73 < 5 => false
right < left
5 < 73 =>true
result.push(5)
indexRight ++

left < right
73 < 5 => false
right < left
5 < 73 => true
result.push(7)=> At this time result = [5,7]
indexRight ++
// I have left at index 0, already organized
// I have this state => result [5,7] left [5,7] at index 1 right[73,90] at index 0
result.concat(left, right)
result [5,7,5,7,73,90]
// if i say result.concat(left.slice(indexLeft), right(slice(inexRight)))
// i would have
//remember indexLeft = 1 => left.slice(1) = []
//indexRight = 0 => right.slice(0)= [73,90]
return result.concat(left.slice(indexLeft), right.slice(indexRight))
result = [5,7,73,90]

and so on for the other side.