Merge

Divide and Conquer

The divide-and-conquer paradigm is a problem-solving strategy that involves breaking down a problem into smaller subproblems, solving each subproblem independently, and then combining the solutions into a final solution for the original problem.

The basic steps of the divide-and-conquer paradigm are:

1. Divide the problem into smaller subproblems.

2. Conquer each subproblem by solving them recursively or iteratively.

3. Combine the solutions of the subproblems into a solution for the original problem.

This strategy is often used in computer science and mathematics to solve complex problems efficiently.

It is especially useful for problems that can be broken down into smaller, independent subproblems, as it enables parallelization and can reduce the overall time complexity of the algorithm.

The divide-and-conquer paradigm can be a powerful tool for solving complex problems efficiently, but it requires careful consideration of how to divide the problem into subproblems and how to combine the solutions of those subproblems.

---

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer paradigm.

It works by dividing the unsorted list into smaller sublists, sorting those sublists recursively, and then merging them back together into the final sorted list.

Here are the basic steps of the Merge Sort algorithm:

1. Divide the unsorted list into two sublists of roughly equal size.

2. Sort each of the sublists recursively by applying the same divide-and-conquer strategy.

3. Merge the sorted sublists back together into one sorted list.

Data Structures and Algorithms Cheatsheet - Algorithms Section - 8

Merge Sort has a time complexity of O(n log n), making it more efficient than quadratic sorting algorithms like Bubble Sort, Selection Sort, and Insertion Sort for large datasets.

Additionally, Merge Sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements.

However, Merge Sort has a relatively high space complexity due to its use of additional memory during the merging process.

pseudocode:

MergeSort(array)
    if length of array <= 1
        return array
    else
        mid = length of array / 2
        left_half = MergeSort(first half of array)
        right_half = MergeSort(second half of array)
        return Merge(left_half, right_half)

Merge(left_half, right_half)
    result = empty array
    while left_half is not empty and right_half is not empty
        if first element of left_half < first element of right_half
            append first element of left_half to result
            remove first element from left_half
        else
            append first element of right_half to result
            remove first element from right_half
    if left_half is not empty
        append remaining elements of left_half to result
    if right_half is not empty
        append remaining elements of right_half to result
    return result

function MergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return merge(MergeSort(left), MergeSort(right));
}

function merge(left, right) {
    let result = [];
    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++;
        }
    }

    while (leftIndex < left.length) {
        result.push(left[leftIndex]);
        leftIndex++;
    }

    while (rightIndex < right.length) {
        result.push(right[rightIndex]);
        rightIndex++;
    }

    return result;
}

console.log(MergeSort(numbers));

Output

PS D:\Coding Playground> node playground2.js
[
    0,  1,  2,  4,  5, 6, 44, 63, 87, 99, 283
]