Buildtide
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.ts
Unsorted [ 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.