TypeScript: Merge Two Sorted Arrays

1. Introduction

Merging two sorted arrays is a common task that is often encountered in the world of algorithms, especially when dealing with the merge sort algorithm. In this guide, we'll look into how we can merge two sorted arrays into a single, sorted array using TypeScript.

2. Program Overview

The basic idea to merge two sorted arrays is to compare the elements of the two arrays and pick the smaller one. We will:

1. Initialize three pointers: one for each of the two arrays and one for the resultant array.

2. Compare the elements where the pointers are pointing in the two input arrays, pick the smaller one, and place it in the resultant array.

3. Increment the pointer of the array from which the element was picked and also increment the resultant array pointer.

4. Repeat the process until one of the input arrays is exhausted.

5. Append the remaining elements from the non-exhausted array to the resultant array.

3. Code Program

function mergeSortedArrays(arr1: number[], arr2: number[]): number[] {
    let i = 0, j = 0;
    const result: number[] = [];

    // Compare elements of arr1 and arr2
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr2[j]);
            j++;
        }
    }

    // Push the remaining elements of arr1, if any
    while (i < arr1.length) {
        result.push(arr1[i]);
        i++;
    }

    // Push the remaining elements of arr2, if any
    while (j < arr2.length) {
        result.push(arr2[j]);
        j++;
    }

    return result;
}

// Test the function
const array1 = [1, 3, 5, 7];
const array2 = [2, 4, 6, 8, 10];
console.log("Merged Sorted Array:", mergeSortedArrays(array1, array2));

Output:

Merged Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 10]

4. Step By Step Explanation

1. We start by initializing three pointers: i for arr1, j for arr2, and the result array where we will be placing the sorted elements.

2. Using a while loop, we compare the current elements of arr1 and arr2 (i.e., arr1[i] and arr2[j]).

3. If the element in arr1 is smaller, we push it to the result array and increment the i pointer. If the element in arr2 is smaller, we push it to the result array and increment the j pointer.

4. Once one of the arrays is exhausted, there might be some remaining elements in the other array. We simply append these to the result array.

5. Finally, our function returns the merged sorted array.

6. We then test our function using two sample sorted arrays and output the merged result.