Hi, I'm Tuan, a Full-stack Web Developer from Tokyo 😊. Follow my blog to not miss out on useful and interesting articles in the future.
Sorting data is a fundamental concept in computer science, and learning how to sort an array is an important step for anyone looking to improve their coding skills. One of the most popular sorting algorithms is called "Merge Sort," and in this article, we'll be taking a closer look at how it works and how you can use it in your own JavaScript projects.
What is Merge Sort?
Merge Sort is an algorithm that takes an array of elements and divides it into smaller sub-arrays. These sub-arrays are then sorted individually, and finally, the sub-arrays are merged back together to form a sorted array.
The reason why this algorithm is called "Merge Sort" is because it uses a process called "merging" to combine the smaller sub-arrays back into a single, sorted array. This process is repeated recursively, breaking down the array into smaller and smaller pieces until each sub-array only contains one element.
The key advantage of using Merge Sort is that it guarantees to sort an array of n elements in O(n * log n) time, making it more efficient than other sorting algorithms like Bubble sort or insertion sort.
function mergeSort(arr) { if (arr.length < 2) { return arr; } let middle = Math.floor(arr.length / 2); let left = arr.slice(0, middle); let right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right));
} function merge(left, right) { let result = []; let i = 0; let j = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) { result.push(left[i++]); } else { result.push(right[j++]); } } return result.concat(left.slice(i)).concat(right.slice(j));
}
How to Use Merge Sort in JavaScript
Now that you understand the basic concepts behind Merge Sort, let's take a look at how you can implement it in JavaScript. Here's an example of a basic implementation:
function mergeSort(arr) { if (arr.length < 2) { return arr; } let middle = Math.floor(arr.length / 2); let left = arr.slice(0, middle); let right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right));
} function merge(left, right) { let result = []; let i = 0; let j = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) { result.push(left[i++]); } else { result.push(right[j++]); } } return result.concat(left.slice(i)).concat(right.slice(j));
}
In this example, we have two functions: mergeSort and merge. The mergeSort function takes an array as its input and uses recursion to break it down into smaller sub-arrays. The merge function then takes two sorted sub-arrays and merges them back together to form a single, sorted array.
Use case
Now that you know how to implement Merge Sort in JavaScript, let's take a look at some real-world examples of where you might use it.
1. Sorting a List of Names
If you have a list of names that you need to sort alphabetically, you can use Merge Sort to do this quickly and efficiently. Here's an example:
let names = ["Alice", "Bob", "Charlie", "David", "Eve"];
console.log(mergeSort(names)); // Output: ["Alice", "Bob", "Charlie", "David", "Eve"]
2. Sorting a List of Numbers
If you have a list of numbers that you need to sort in ascending or descending order, you can use Merge Sort to accomplish this as well. Here's an example of how you might sort a list of numbers in ascending order:
let numbers = [4, 2, 5, 1, 3];
console.log(mergeSort(numbers)); // Output: [1, 2, 3, 4, 5]
3. Sorting a List of Objects
Merge Sort can also be used to sort a list of objects based on a specific property. Here's an example of how you might sort a list of objects containing information about people by their last name:
let people = [ {firstName: "John", lastName: "Doe"}, {firstName: "Jane", lastName: "Smith"}, {firstName: "Bob", lastName: "Johnson"}
]; function compare(a, b) { if (a.lastName < b.lastName) { return -1; } if (a.lastName > b.lastName) { return 1; } return 0;
} console.log(mergeSort(people, compare));
/* Output: [ { firstName: 'Bob', lastName: 'Johnson' }, { firstName: 'John', lastName: 'Doe' }, { firstName: 'Jane', lastName: 'Smith' } ]
*/
4. Sorting a List of Custom Data Structures
In addition to simple data types like strings and numbers, Merge Sort can also be used to sort custom data structures like linked lists or binary trees. Here's an example of how you might use Merge Sort to sort a linked list:
class Node { constructor(value) { this.value = value; this.next = null; }
} class LinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } //.. push, mergeSort(linkedlist) methods
}
let list = new LinkedList();
list.push(5);
list.push(2);
list.push(4);
list.push(1);
list.push(3);
list = mergeSort(list);
//.. traversing through linkedlist
5. Sorting Large Amounts of Data
Because Merge Sort has a guaranteed time complexity of O(n * log n), it's well-suited for sorting large amounts of data. This makes it a great choice for use in big data or data science applications.
let largeData = Array.from({length: 1000000}, () => Math.floor(Math.random()*100000))
console.log("Before Sort: ", largeData.slice(0,5));
largeData = mergeSort(largeData);
console.log("After Sort: ", largeData.slice(0,5));
Conclusion
Merge Sort is a powerful and efficient sorting algorithm that can be used to sort a wide range of data types, from simple arrays of numbers and strings to more complex data structures like linked lists and binary trees. The key advantage of Merge Sort is its guaranteed time complexity of O(n * log n), which makes it well-suited for sorting large amounts of data. With this guide and the provided examples, you now have the knowledge to implement Merge Sort in your own JavaScript projects and improve your coding skills.
As always, I hope you enjoyed this article and learned something new. Thank you and see you in the next articles!
If you liked this article, please give me a like and subscribe to support me. Thank you. 😊