Skip to content

Instantly share code, notes, and snippets.

@ycmjason
Last active April 24, 2019 15:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ycmjason/35a46672c9db12b0840a3d10b342887f to your computer and use it in GitHub Desktop.
Save ycmjason/35a46672c9db12b0840a3d10b342887f to your computer and use it in GitHub Desktop.
Merge sort
const mergeSort = (xs) => {
if (xs.length <= 1) return xs;
const midIndex = Math.trunc(xs.length / 2);
return merge(
mergeSort(xs.slice(0, midIndex)),
mergeSort(xs.slice(midIndex)),
);
}
const merge = (xs, ys) => {
if (xs.length <= 0) return ys;
if (ys.length <= 0) return xs;
return xs[0] < ys[0]
? [xs[0], ...merge(xs.slice(1), ys)]
: [ys[0], ...merge(xs, ys.slice(1))];
};
const mergeSort = (xs: number[]): number[] => {
if (xs.length <= 1) return xs;
const midIndex: number = Math.trunc(xs.length / 2);
return merge(
mergeSort(xs.slice(0, midIndex)),
mergeSort(xs.slice(midIndex))
);
}
const merge = (xs: number[], ys: number[]): number[] => {
if (xs.length <= 0) return ys;
if (ys.length <= 0) return xs;
return xs[0] < ys[0]
? [xs[0], ...merge(xs.slice(1), ys)]
: [ys[0], ...merge(xs, ys.slice(1))];
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment