Author: Hussain Mir Ali

I am interested in web and mobile technologies.

If you have any questions or feedback then message me at devtips@Buildtide.com.

# Algorithms #2: Merge Sort using TypeScript

In this post if have implemented Merge sort using TypeScript.
This algorithm has the following characteristics:

Worst case time:  O(nlogn)

Worst case space: O(n)

Implementation:

`/** * This class contains logic for Merge Sort algorithm implementation.  *  * @class MergeSort * @constructor */export class MergeSort {  private temp: number[] = [];  constructor() {}    /**     * Starts the soring process.     *     * @method sort     * @param {Array} arry The array to be sorted.     */  public sort(arry: number[]): void {    if (arry !== undefined) {      this.mergeSort(arry, this.temp, 0, arry.length - 1);    }  }  /**   * Recursively sorts and calls merge.   *   * @method mergeSort   * @param {Array} arr The array to be sorted.   * @param {Array} temp The temporary array.   * @param {Number} left The left index of the array.   * @param {Number} right The right index of the array.   */  public mergeSort(arr: number[], temp: number[], left: number, right: number): void {    if (left < right) {      let center: number = Math.floor((left + right) / 2);      this.mergeSort(arr, temp, left, center);      this.mergeSort(arr, temp, center + 1, right);      this.merge(arr, temp, left, center + 1, right);    }  }  /**   * This method contains the logic to implement the merge step.   *   * @method merge   * @param {Array} arr The array to be sorted.   * @param {Array} temp The temporary array.   * @param {Number} left The left index of the array.   * @param {Number} right The right index of the array.    * @param {Number} rightEnd The right most index of the array.     */  public merge(arr: number[], temp: number[], left: number, right: number, rightEnd: number): void {    let leftEnd: number = right - 1;    let k: number = left;    let num: number = rightEnd - left + 1;    while (left <= leftEnd && right <= rightEnd) {      if (arr[left] <= arr[right]) {        temp[k++] = arr[left++];      } else {        temp[k++] = arr[right++]      }    }    while (left <= leftEnd) {      temp[k++] = arr[left++];    }    while (right <= rightEnd) {      temp[k++] = arr[right++];    }    for (let i: number = 0; i < temp.length; i++, rightEnd--) {      arr[rightEnd] = temp[rightEnd];    }  }}`

Usage:
`import {MergeSort} from './Mergesort'let arry:number[] = [];for(let i = 0; i<15; i++){ arry[i] =Math.floor(Math.random() * 16) + 1;}console.log('Unsorted',arry);let sorter:MergeSort = new MergeSort();sorter.sort(arry);console.log('Sorted',arry);`

Output:
`hxce@ubuntu:~/Desktop/MergeSort\$ ts-node main.tsUnsorted [ 16, 9, 9, 12, 6, 11, 7, 10, 3, 16, 4, 9, 4, 4, 15 ]Sorted [ 3, 4, 4, 4, 6, 7, 9, 9, 9, 10, 11, 12, 15, 16, 16 ]`

### ðŸ’¡ Practice Coding

Practice coding questions from top companies like Google, Amazon, Apple, and others. Signup today at Softnami's daily coding.