merge-sort.asc

Merge Sort

Merge Sort is an efficient sorting algorithm that uses divide and conquer paradigm to accomplish its task faster. However, It uses auxiliary memory in the process of sorting.

Merge sort algorithm splits the array into halves until 2 or fewer elements are left. It sorts these two elements and then merges back all halves until the whole collection is sorted.

Merge Sort Implementation

Merge Sort implementation in JavaScript (mergeSort)

link:../../../src/algorithms/sorting/merge-sort.js[role=include]

1. Convert any kind of iterable (array, sets, etc.) into an array

As you can see this function is just a wrapper to transform things into an array. The heavy lifting is done in splitSort as you can see below.

Merge Sort implementation in JavaScript (splitSort)

link:../../../src/algorithms/sorting/merge-sort.js[role=include]

1. Base case: Sort two or less items manually.

2. Recursively divide the array in half until two or less elements are left.

3. Merge back the sorted halves in ascending order.

Let’s take a look at the merge function:

Merge Sort implementation in JavaScript (merge)

link:../../../src/algorithms/sorting/merge-sort.js[role=include]

1. We need to keep track of 3 arrays indices: index which keeps track of the combined array position, i1 which is the array1 index and a2 for array2.

2. If array1 current element (i1) has the lowest value, we insert it into the mergedArray if not we then insert array2 element.

3. mergedArray is array1 and array2 combined in ascending order (sorted).

Merge sort has an O(n log n) running time. For more details about how to extract the runtime go to part01-algorithms-analysis.asc section.

Merge Sort Properties

• [Stable]: ✅ Yes

• [In-place]: ️❌ No, it requires auxiliary memory O(n).

• [Online]: ️❌ No, new elements will require to sort the whole array.

• [Adaptive]: ️❌ No, mostly sorted array takes the same time O(n log n).

• Recursive: Yes

• Time Complexity: ✅ part01-algorithms-analysis.asc O(n log n)

• Space Complexity: ⚠️ part01-algorithms-analysis.asc O(n), use auxiliary memory