Softnami
Author: Hussain Mir Ali

I am interested in web and mobile technologies.

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

Announcements
Ads

Call predictor: AI based call prediction

Download

2020

Feb
Jan

2019

Dec
Nov
Jul
May
Mar
Jan

2018

Nov
Sep
Jul
Jun
Apr
Feb
Jan

2017

Dec
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Jan

2016

Dec
Oct
Sep
Aug
Jul

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.