DEV Community

Code_Regina
Code_Regina

Posted on

Merge Sort

                   -Merge Sort: Introduction
                   -Merge Arrays: Implementation
Enter fullscreen mode Exit fullscreen mode

Merge Sort: Introduction

Merge sorting is a combination of merging and sorting, works by decomposing an array into smaller arrays, also known as a divide and conquer strategy. The process split up larger array into smaller sub arrays all the way down until get to 0 or 1 element, then building up a newly sorted array.

Alt Text

Merge Arrays: Implementation

Merge Sort Example


function merge(arr1, arr2){
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) {
        results.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j])
        j++;
    }
    return results;
}
merge([100,200], [1,2,3,5,6])


Enter fullscreen mode Exit fullscreen mode

Most merge sort implementation use recursion.


function merge(arr1, arr2){
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) {
        results.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j])
        j++;
    }
    return results;
}

//Recrusive Merge Sort
function mergeSort(arr){
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0,mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, sright);
}

mergeSort([10,24,76,73])

Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
im6h profile image
Vu

You still use arr functions instead of pure use like C / C ++ language, I tried to implement mergesort with Typescript on tsplayground like it doesn't really work.