Programmatic Approach for Merge Sort
- First create a recursive function mergeSort the divide the array into halves again and again by findiing the middle index and call mergesort again for left and right halves.
- Define a function merge that will be called to sort and merge the subarrays and will be called after the mergeSort function returns.
- Inside merge function take new subarrays divided by mergeSort and start the merge process
- Merge the subarrays in a way that the smallar element is put first in the array on every iteration and after one is finished push the second subarray completely.
- It process starting from the unit subarray will continue till the whole array is merged and sorted completely.
Example: The code implementation of the merge sort is as follows.
// Function to merge two sorted parts of array
function merge(arr, left, middle, right) {
// Length of both sorted aub arrays
let l1 = middle - left + 1;
let l2 = right - middle;
// Create new subarrays
let arr1 = new Array(l1);
let arr2 = new Array(l2);
// Assign values in subarrays
for (let i = 0; i < l1; ++i) {
arr1[i] = arr[left + i];
}
for (let i = 0; i < l2; ++i) {
arr2[i] = arr[middle + 1 + i];
}
// To travesrse and modify main array
let i = 0,
j = 0,
k = left;
// Assign the smaller value for sorted output
while (i < l1 && j < l2) {
if (arr1[i] < arr2[j]) {
arr[k] = arr1[i];
++i;
} else {
arr[k] = arr2[j];
j++;
}
k++;
}
// Update the remaining elements
while (i < l1) {
arr[k] = arr1[i];
i++;
k++;
}
while (j < l2) {
arr[k] = arr2[j];
j++;
k++;
}
}
// Function to implement merger sort in javaScript
function mergeSort(arr, left, right) {
if (left >= right) {
return;
}
// Middle index to create subarray halves
let middle = left + parseInt((right - left) / 2);
// Apply mergeSort to both the halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge both sorted parts
merge(arr, left, middle, right);
}
// Input array
const arr = [ 38, 27, 43, 10]
// Display input array
console.log("Original array: " + arr);
// Apply merge sort function
mergeSort(arr, 0, arr.length - 1);
// Display output
console.log("After sorting: " + arr);
Output
Original array: 38,27,43,10 After sorting: 10,27,38,43