Sahil Bondre

Posted on

# ðŸŒˆ Merge Sort & Quick Sort in 5 Languages

I am starting this new series wherein I analyse the code for algorithms in 5 languages: C++, Dart, Go, JavaScript and TypeScript. For this post, I'll be comparing two of the most popular sorting algorithms: Quick Sort and Merge Sort.

# Merge Sort

Merge sort is a divide and conquer algorithm. We divide the array into two sub-parts. Then we call `mergeSort` on both these sub-parts. This is the recursive step of merge sort. After this, we have two sorted arrays. We call the `merge` algorithm which converts these two sorted arrays into a single combined sorted array.

Time Complexity: O(nlogn)
Space Complexity: O(n)

Code is in this repo.

## C++

If you find `foo[i++] = bar` weird, it's equivalent to `foo[i] = bar` followed by `i++`.

## Dart

`a ~/ b` returns and `int` on division (and not `double`).

# Quick Sort

Quick Sort is also a divide and conquer algorithm. We first choose a `pivot` element. Then we divide the array in such a way that, elements smaller than `pivot` come before pivot and elements larger than `pivot` come later. Then we recursively call `quickSort` on each of the smaller sub-arrays.

Time Complexity: O(nlogn)
Space Complexity: O(logn) [Due to recursive calls]

All the code in this repo.

## TypeScript

ðŸŒˆ Code for this series is in this repo (Star it!)
ðŸš€ Find me on Instagram | Github | Twitter | Website
ðŸ˜„ Have a wonderful day!