가장 먼저 실전에 응용된 정렬 알고리즘.
분할과 정복이 핵심.
const mergeSort = () => {
array = mergeSortRec(array);
}
let mergeSortRec = (array) => {
let length = array.length;
if(length === 1){
return array;
}
let mid = Math.floor(length/2),
left = array.slice(0, mid),
right = array.slice(mid, length);
return merge(lergeSortRec(left),mergeSortRec(right));
}
let merge = (left,right) => {
let result = [],
il =0,
ir =0;
while(il < left.length && ir < right.length){
if(left[il] < right[ir]){
result.push(left[il++]);
}else{
result.push(right[ir++]);
}
}
while(il < left.length){
result.push(left[il]);
}
while(ir < right.length){
result.push(right[ir])
}
return result;
}