Hello, aspiring TypeScript developers!

In today's lesson, we're diving into merge sort, a powerful algorithm for organizing data efficiently. Picture shuffling a deck of cards and then rearranging them in order. Merge sort achieves this with data on a grand scale, making it an excellent choice for sorting large datasets. We're going to explore and implement this technique using TypeScript.

First, let's construct a merge() function in TypeScript. This function merges two sorted arrays into a single sorted array. Think of it as combining two sorted stacks of cards into one sorted stack.

TypeScript
Copy to clipboard
1function merge(left: number[], right: number[]): number[] {
2    let resultArray: number[] = [];
3    let leftIndex = 0, rightIndex = 0;
4
5    // sorting and merging process
6    while (leftIndex < left.length && rightIndex < right.length) {
7        if (left[leftIndex] < right[rightIndex]) {
8            resultArray.push(left[leftIndex]);
9            leftIndex++;
10        } else {
11            resultArray.push(right[rightIndex]);
12            rightIndex++;
13        }
14    }
15
16    return resultArray
17        .concat(left.slice(leftIndex))
18        .concat(right.slice(rightIndex));
19}

The merge() function above takes two sorted arrays (left and right) and combines them into one sorted array (resultArray).

Seemingly tricky, the code is very straightforward:

1. We place two pointers, leftIndex and rightIndex, at the beginning of the left and right arrays.
2. We choose the smaller element, put it in the final array resultArray, and move the corresponding pointer further.
3. We keep doing this until one of the pointers reaches the end of its array.

We stop the process when one of the pointers reaches the end of its array, but some elements could be left in the other array.

To handle this, we copy the remaining elements of both arrays (if any) to the end of the resulting arr array, using .concat method.

Now, we will implement the complete merge sort algorithm in TypeScript. This involves splitting an array into halves until each sub-array contains only one element. Arrays with a single element are inherently sorted, allowing us to merge them back into a sorted whole.

TypeScript
Copy to clipboard
1function mergeSort(unsortedArray: number[]): number[] {
2    if (unsortedArray.length <= 1) {
3        return unsortedArray; // If the array has only one element, it's already sorted
4    }
5
6    const middle: number = Math.floor(unsortedArray.length / 2); // This will get the midpoint of the array
7    const left: number[] = unsortedArray.slice(0, middle); // We split the array into two halves
8    const right: number[] = unsortedArray.slice(middle); // This is the right half
9
10    // Merge the two halves back together
11    return merge(
12        mergeSort(left), mergeSort(right)
13    );
14}

Voila! You've successfully decoded the Merge Sort algorithm in TypeScript!

Merge sort is known for its consistent performance with a time complexity of $O(n \log n)$, especially when dealing with large datasets. One drawback is its extra memory usage during the merge process. Using TypeScript with merge sort not only brings these benefits but also adds type safety, making your sorting implementations more error-resistant and reliable.

Congratulations! You've unlocked the potential of the merge sort algorithm using TypeScript. By understanding its strengths, such as $O(n \log n)$ time complexity, you're well-prepared to tackle data organization tasks efficiently.

Stay tuned for hands-on practice exercises and further exploration of merge sort within TypeScript. Get ready to solve engaging problems and deepen your coding expertise!