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:

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:

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.