Skip to content

Instantly share code, notes, and snippets.

@venil7
Created June 2, 2020 19:42
Show Gist options
  • Save venil7/7268799a68983517cb3d2fb3e6f3ec4e to your computer and use it in GitHub Desktop.
Save venil7/7268799a68983517cb3d2fb3e6f3ec4e to your computer and use it in GitHub Desktop.
Merge Sort (TypeScript)
const sort = (a: number[]): number[] => {
const split = (a: number[]): [number[], number[]] => {
const take_left = Math.ceil(a.length / 2);
const take_right = Math.ceil(a.length / 2);
const left = a.slice(0, take_left);
const right = a.slice(take_right);
return [left, right];
};
const merge = (a: number[], b: number[]): number[] => {
if (a.length === 0) return b;
if (b.length === 0) return a;
const [a1, ...a_rest] = a;
const [b1, ...b_rest] = b;
return (a1 < b1) ? [a1, ...merge(a_rest, b)] : [b1, ...merge(b_rest, a)];
};
if (a.length < 2) return a;
const [left, right] = split(a);
return merge(sort(left), sort(right));
};
console.log(sort([1, 9, 2, 8, 3, 7, 4, 6, 5]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment