Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Cover image for How “Merge Sort” works in JavaScript?
Jaimal Dullat
Jaimal Dullat

Posted on • Edited on

     

How “Merge Sort” works in JavaScript?

Hello there! Today, we will delve into the world of sorting algorithms, specifically focusing on the Merge Sort algorithm. We’ll use JavaScript to illustrate how this algorithm works. If you’re a beginner, don’t worry! This guide is designed to be simple and easy to understand.


What is Merge Sort?

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer programming paradigm.

It works by repeatedly dividing the unsorted list into two halves until we reach a stage where we can no longer divide (i.e., we have individual elements). We then merge these individual elements back together in a sorted manner.


The Merge Sort Process

To understand Merge Sort, let’s consider a simple array of numbers:

[38,27,43,3,9,82,10]
Enter fullscreen modeExit fullscreen mode

Here’s how Merge Sort would tackle this:

1. Divide: Break the array into halves until you have arrays with single elements:

[38,27,43,3,9,82,10][38,27,43]and[3,9,82,10][38][27,43]and[3,9][82,10][38][27][43]and[3][9][82][10]
Enter fullscreen modeExit fullscreen mode

2. Conquer (Merge): Starting from the smallest arrays, merge them back together in a sorted manner:

[27,38][43]and[3,9][10,82][27,38,43]and[3,9,10,82][3,9,10,27,38,43,82]
Enter fullscreen modeExit fullscreen mode

Voila! The array is sorted.

Now, let’s see how we can implement this algorithm in JavaScript.


Implementing Merge Sort in JavaScript

First, we need to create a function that can merge two sorted arrays into one sorted array. Let’s call this function merge:

functionmerge(left,right){letresultArray=[],leftIndex=0,rightIndex=0;// Loop through both arrays, comparing elements and adding the smaller one to the resultArraywhile(leftIndex<left.length&&rightIndex<right.length){if(left[leftIndex]<right[rightIndex]){resultArray.push(left[leftIndex]);leftIndex++;// Move to the next element in the `left` array}else{resultArray.push(right[rightIndex]);rightIndex++;// Move to the next element in the `right` array}}// Concatenate the remaining elements from either `left` or `right` (if any)returnresultArray.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));}
Enter fullscreen modeExit fullscreen mode

Next, we will create our mergeSort function:

functionmergeSort(array){// Base case: If the array has only one element, return it (already sorted)if(array.length===1){returnarray;}// Divide the array into two halvesconstmiddle=Math.floor(array.length/2);// Find the middle indexconstleft=array.slice(0,middle);// Split the array into left halfconstright=array.slice(middle);// Split the array into right half// Recursively call mergeSort on the left and right halvesreturnmerge(mergeSort(left),// Recursively sort the left halfmergeSort(right)// Recursively sort the right half);}
Enter fullscreen modeExit fullscreen mode

You can now sort an array by calling mergeSort with the array as an argument:

console.log(mergeSort([38,27,43,3,9,82,10]));
Enter fullscreen modeExit fullscreen mode

And there you have it! You’ve successfully implemented the Merge Sort algorithm in JavaScript.


Breakdown

let’s break down the execution of the Merge Sort algorithm step by step for the array [38, 27, 43, 3, 9, 82, 10].

Step 1: Initial Array

Input Array:[38, 27, 43, 3, 9, 82, 10]

Step 2: Initial Split

  • Divide the array into two halves:[38, 27, 43] and[3, 9, 82, 10].

Step 3: Further Division

  • Divide[38, 27, 43] into[38],[27],[43].

  • Divide[3, 9, 82, 10] into[3, 9],[82, 10].

Step 4: Merging Single Elements

  • The individual elements are already sorted as each sub-array has only one element.

Step 5: Merging Sub-Arrays

  • Merge[38] and[27] to get[27, 38].

  • Merge[43] with[27, 38] to get[27, 38, 43].

  • Merge[3] and[9] to get[3, 9].

  • Merge[82] and[10] to get[10, 82].

Step 6: Final Merge

  • Merge [3, 9] and [10, 82] to get [3, 9, 10, 82].

Step 7: Final Merging of Halves

  • Merge[27, 38, 43] and[3, 9, 10, 82] to get the final sorted array:[3, 9, 10, 27, 38, 43, 82].

This process involves recursively splitting the array until it contains only single elements, then merging them back together in sorted order at each step until the final sorted array is obtained.


Conclusion

Merge Sort is an efficient, stable sorting algorithm that performs well on large data sets.

While it may seem complex at first, breaking it down step-by-step makes it easier to understand.

I hope this guide has helped illuminate the inner workings of Merge Sort, and that you now feel more comfortable with this essential algorithm.

🔥 Wait! 🔥

Give that like button some love! And if you’re feeling extra cheeky, hit follow too!

Follow me on Instagram:Click Here

Top comments(3)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss
CollapseExpand
 
dsaga profile image
Dusan Petkovic
Front-end software engineer with full-stack experience eager to learn new things to find material for my blog :/
  • Location
    Paracin, Serbia
  • Pronouns
    he/him
  • Joined

The animation is great, I can almost understand it lol.. jk

I understand from a general perspective, these kinds of things need to be practiced a few times, maybe even without the code editor.

CollapseExpand
 
dsaga profile image
Dusan Petkovic
Front-end software engineer with full-stack experience eager to learn new things to find material for my blog :/
  • Location
    Paracin, Serbia
  • Pronouns
    he/him
  • Joined

The code doesn't make it much easier to understand, so its probably always better to write down on paper

CollapseExpand
 
jaimaldullat profile image
Jaimal Dullat
JavaScript Nerd | Full Stack Developer
  • Location
    Canada
  • Joined

I agreed. Recursion is a confusing concept even for experienced developers. I know animation doesn't show how the Recursion works, it's just a general working of Merge Sort which helps to understand it a bit easier.

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

JavaScript Nerd | Full Stack Developer
  • Location
    Canada
  • Joined

More fromJaimal Dullat

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp