912. Sort an Array Merge Sort
leetcode
Problem:
Given an array of integers, sort the array in ascending order using the merge sort algorithm.
Solution Description:
To implement a merge sort, we need to follow the divide-and-conquer strategy:
- Divide: Split the array into two halves.
- Conquer: Recursively sort each half.
- Combine: Merge the two sorted halves to produce the sorted array.
The merge sort algorithm has a time complexity of O(n log n) because the array is recursively divided in half for log n levels, and each level has a linear operation of merging two halves. The space complexity is O(n) due to the usage of additional space for merging purposes.
Example:
Consider the array [5, 2, 3, 1]:
- Divide it into two halves: [5, 2] and [3, 1]
- Recursively sort each half: [2, 5] and [1, 3]
- Merge the sorted halves: [1, 2, 3, 5]
Setup:
We will define the main function `mergeSort` to handle the recursion and `merge` function to merge two sorted arrays. For simplicity, we will use temporary arrays to store smaller segments while merging.
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
// Helper functions for logging
const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;
log('nums initial:');
table(nums);
if (nums.length < 2) return nums;
/**
* @param {number[]} left
* @param {number[]} right
*/
function merge(left, right) {
let res = [];
let l = 0;
let r = 0;
while (l < left.length || r < right.length) {
if (l === left.length) {
while (r < right.length) res.push(right[r++]);
} else if (r === right.length) {
while (l < left.length) res.push(left[l++]);
} else {
if (left[l] <= right[r]) res.push(left[l++])
else res.push(right[r++])
}
}
return res;
}
//log(merge([1, 4], [3, 3, 5, 6]));
/**
* @param {number[]} arr
* @returns {number[]}
*/
function sort(arr) {
if (arr.length < 2) return arr;
const mid = Math.floor(arr.length / 2);
const left = sort(arr.slice(0, mid));
const right = sort(arr.slice(mid));
//log(`mid = '${mid}'; left = '${left}'; right = '${right}';`);
return merge(left, right);
}
// log(sort([1, 3, 1, 2]))
return sort(nums);
};
// Test cases
const testCases = [
{ array: [5, 2, 3, 1], expected: [1, 2, 3, 5] },
{ array: [5, 1, 1, 2, 0, 0], expected: [0, 0, 1, 1, 2, 5] },
{ array: [], expected: [] },
{ array: [10, 5, 2, 3, 7, 1, 9, 8], expected: [1, 2, 3, 5, 7, 8, 9, 10] },
{ array: [1], expected: [1] },
];
testCases.forEach((test, index) => {
const result = sortArray(test.array) || 'undefined';
console.log(`Test Case ${index + 1}: ${result.toString() === test.expected.toString() ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});