I am trying to understand all sorting algos and this is the code I have written for merge sort, but its not working, can you please point out the error in it :
solve: function (A) {
let count = this.mergeSort(A);
return count;
},
mergeTwoSortedArrays: function (A, B) {
let i = 0;
let j = 0;
let k = 0;
let C = [];
while (i < A.length && j < B.length && A[i] || B[j]) {
if (A[i] < B[j]) {
C[k] = A[i];
i++;
k++;
}
else {
C[k] = B[j];
j++;
k++;
}
}
while (j < B.length) {
C[k] = B[j];
k++;
j++;
}
while (i < A.length) {
C[k] = A[i];
k++;
i++;
}
return C;
},
mergeSort: function (a) {
let n = a.length;
if (n <= 1) return a;
let c = Array.from({ length: Math.floor(n / 2) }, (_, i) => a[i]);
let d = Array.from({ length: n - c.length }, (_, i) => a[c.length + i]);
return this.mergeTwoSortedArrays(c, d);
}
Well the question is asking me to add more details for my post to be approved.
So my approach here is : divide the array into two equal parts until they become array of 1 element and then use merge technique to merge two sorted arrays.
>Solution :
You should simply check i < A.length && j < B.length as the loop condition.
Here is your updated code:
const mergeSort = {
solve: function (A) {
return this.mergeSortFunction(A);
},
mergeTwoSortedArrays: function (A, B) {
let i = 0;
let j = 0;
let k = 0;
let C = [];
while (i < A.length && j < B.length) {
if (A[i] < B[j]) {
C[k] = A[i];
i++;
k++;
} else {
C[k] = B[j];
j++;
k++;
}
}
while (j < B.length) {
C[k] = B[j];
k++;
j++;
}
while (i < A.length) {
C[k] = A[i];
k++;
i++;
}
return C;
},
mergeSortFunction: function (a) {
let n = a.length;
if (n <= 1) return a;
let c = Array.from({ length: Math.floor(n / 2) }, (_, i) => a[i]);
let d = Array.from({ length: n - c.length }, (_, i) => a[c.length + i]);
return this.mergeTwoSortedArrays(this.mergeSortFunction(c), this.mergeSortFunction(d));
}
};
// Example
const inputArray = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = mergeSort.solve(inputArray);
console.log(sortedArray);
// Output: [3, 9, 10, 27, 38, 43, 82]