JavaScript: Marge sort - recursion

JavaScript Function: Exercise-9 with Solution

Merge Sort

Write a merge sort program in JavaScript.

Sample array : [34,7,23,32,5,62]
Sample output : [5, 7, 23, 32, 34, 62]

Visual Presentation:

Sample Solution-1:

JavaScript Code:

// Extend Array prototype to include a merge sort function
Array.prototype.merge_Sort = function () {
 // Base case: If the array has 1 or fewer elements, it is already sorted
 if (this.length <= 1) { return this; } // Calculate the middle index var half = parseInt(this.length / 2); // Recursively sort the left and right halves of the array var left = this.slice(0, half).merge_Sort(); var right = this.slice(half, this.length).merge_Sort(); // Merge function to combine two sorted arrays var merge = function (left, right) { var mergedArray = []; // While both left and right arrays have elements while (left.length> 0 && right.length> 0) {
 // Compare the first elements of left and right, push the smaller one to the mergedArray
 mergedArray.push((left[0] <= right[0]) ? left.shift() : right.shift()); } // Concatenate any remaining elements in left and right to the mergedArray return mergedArray.concat(left).concat(right); }; // Return the merged result of sorting the left and right halves return merge(left, right); }; // Example usage: Perform merge sort on an array var inputArray = [34, 7, 23, 32, 5, 62]; var sortedArray = inputArray.merge_Sort(); // Output the sorted array console.log(sortedArray); 

Output:

[5,7,23,32,34,62]

Flowchart:

Flowchart: JavaScript recursion function- Marge sort - recursion

Live Demo:

See the Pen javascript-recursion-function-exercise-9 by w3resource (@w3resource) on CodePen.

Sample Solution-2:

JavaScript Code:

 // Merge function to combine two sorted arrays
function merge(left, right) {
 let mergedArray = [];
 let leftIndex = 0;
 let rightIndex = 0;
 // Compare elements from left and right arrays and merge them
 while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] <= right[rightIndex]) { mergedArray.push(left[leftIndex]); leftIndex++; } else { mergedArray.push(right[rightIndex]); rightIndex++; } } // Concatenate any remaining elements in left and right return mergedArray.concat(left.slice(leftIndex), right.slice(rightIndex)); } // Merge sort function using recursion function mergeSort(array) { // Base case: If the array has 1 or fewer elements, it is already sorted if (array.length <= 1) { return array; } // Calculate the middle index const middle = Math.floor(array.length / 2); // Recursively sort the left and right halves of the array const left = mergeSort(array.slice(0, middle)); const right = mergeSort(array.slice(middle)); // Return the merged result of sorting the left and right halves return merge(left, right); } // Example usage: Perform merge sort on an array const inputArray = [34, 7, 23, 32, 5, 62]; const sortedArray = mergeSort(inputArray); // Output the sorted array console.log(sortedArray); 

Output:

[5,7,23,32,34,62]

Flowchart:

Flowchart: JavaScript recursion function- Marge sort - recursion

For more Practice: Solve these Related Problems:

• Write a JavaScript function that implements merge sort recursively and counts the number of comparisons made.
• Write a JavaScript function that performs merge sort and demonstrates in-place merging of subarrays.
• Write a JavaScript function that uses recursion in merge sort to sort subarrays and then merge them.
• Write a JavaScript function that validates the input array before applying merge sort and handles non-numeric elements.

Improve this sample solution and post your code through Disqus.

Previous: Write a JavaScript program for binary search.
Next:Check a string for palindromes using recursion.