DEV Community

Code_Regina
Code_Regina

Posted on

Merge Sort

#javascript #html #css #webdev 
 -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.