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 two 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 fewer 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 i2 for array2.

2. If array1 current element (i1) has the lowest value, we insert it into the mergedArray. If not we then insert the 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