How to use Merge Sort with TypeScript ?
Merge sort follows the divide and conquer approach, which means it breaks the problem into smaller sub-problems, solves each sub-problem, and then combines the solutions to solve the original problem.
How does merge sort work?
Begin with a Recursive Divide and Conquer Approach:
- Start with a recursive function called mergeSort() that takes an array as input.
- Within this function, check if the array length is 0 or 1. If so, return the array as it is already sorted.
- Otherwise, find the middle index of the array and divide it into two halves.
Call mergeSort Recursively:
- Call mergeSort() recursively on the left and right halves of the array to sort them individually.
Define the Merge Function:
- Define a function named merge that takes two sorted arrays (left and right) as input.
- Initialize an empty array called result to store the merged result.
- Initialize variables leftIndex and rightIndex to track the indices of the left and right arrays, respectively.
Merge the Subarrays:
- Iterate through both arrays simultaneously until one of them is fully traversed.
- Compare elements at the current indices of the left and right arrays.
- If the element in the left array is smaller, push it to the result array and move to the next element in the left array.
- If the element in the right array is smaller, push it to the result array and move to the next element in the right array.
Concatenate Remaining Elements:
- After one of the arrays is fully traversed, concatenate the remaining elements of the other array to the result array.
Return the Merged Result:
- Return the merged result array.
Approach:
- Create a recursive function named mergeSort() to divide the passed array into two parts and recursively do the same thing by calling itself again and again until the length of array becomes 0 or 1.
- Define another function named merge() to merge the sorted sub parts of the array and store them in a single sorted array.
- The merge function will merge the arrays in such a way that the smaller elements will be pushed first and larger at last.
- This process will repeat itself untile the whole array gets sorted and merged.
Example: The below code example is a practical implementation of the merge sort in TypeScript.
Javascript
function mergeSort(array: any[]): any[] { if (array.length <= 1) { return array; } const middle = Math.floor(array.length / 2); const leftHalf = array.slice(0, middle); const rightHalf = array.slice(middle); return merge(mergeSort(leftHalf), mergeSort(rightHalf)); } function merge(left: any[], right: any[]): any[] { let result: any[] = []; let leftIndex = 0; let rightIndex = 0; while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { result.push(left[leftIndex]); leftIndex++; } else { result.push(right[rightIndex]); rightIndex++; } } return result.concat(left.slice(leftIndex)). concat(right.slice(rightIndex)); } const sortedNumberArray: number[] = mergeSort([38, 27, 43, 10]); const sortedStringArray: string[] = mergeSort([ 'JavaScript' , 'w3wiki' , 'TypeScript' ]); console.log(sortedNumberArray); console.log(sortedStringArray); |
Output
[10, 27, 38, 43]
["w3wiki", "JavaScript", "TypeScript"]
Time and Space Complexities:
- Time Complexity: Merge sort has a time complexity of O(n log n) in the worst-case scenario. This is because it divides the array into halves recursively and merges them in linear time.
- Space Complexity: Merge sort has a space complexity of O(n) due to the need for auxiliary space for merging the sub-arrays. However, in practice, it’s often considered out-of-place, meaning it requires additional space proportional to the size of the input array.