<pre class="language-typescript"><code class="language-typescript">// O(nlogn) time; O(n) space;
function mergeSort(arr: number[], startIndex = 0, endIndex = arr.length - 1) {
 if (!arr.length || endIndex === startIndex) return;
 const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);
 mergeSort(arr, startIndex, middleIndex);
 mergeSort(arr, middleIndex + 1, endIndex);
 merge(arr, startIndex, middleIndex, endIndex);
}

// O(n^2) time; O(1) space;
function merge(
 arr: number[],
 left: number,
 middle: number,
 right: number
): void {
 let leftIndex = left;
 let rightIndex = middle + 1;
 while (leftIndex &lt;= middle &amp;&amp; rightIndex &lt;= right) {
 const leftNum = arr[leftIndex];
 const rightNum = arr[rightIndex];
 if (leftNum &lt; rightNum) {
 // leftNum is at the correct position
 leftIndex++;
 } else {
 // insert rightNum before leftNum, all elements in between should be shifted one to the right
 for (let i = rightIndex - 1; i &gt;= leftIndex; i--) {
 arr[i + 1] = arr[i];
 }
 arr[leftIndex] = rightNum;

 // increment all pointers
 rightIndex++;
 middle++;
 leftIndex++;
 }
 }
}

// Example
const arr = [5, 4, 3, 2, 1];
mergeSort(arr);
console.log(arr);
</code></pre>

TypeScript solution

Even for Front-End Engineer, it is a must to understand how basic sorting algorithms work. Now you are asked to implement Merge Sort, which sorts an i…