loading...

🌈 Merge Sort & Quick Sort in 5 Languages

godcrampy profile image Sahil Bondre ・2 min read

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++

Alt Text

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

Dart

Alt Text

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

Go

Alt Text

JavaScript

Alt Text

TypeScript

Alt Text

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.

C++

Alt Text

Dart

Alt Text

Go

Alt Text

JavaScript

Alt Text

TypeScript

Alt Text

🌈 Code for this series is in this repo (Star it!)
🌟 I made some Cheat-Sheets
🚀 Find me on Instagram | Github | Twitter | Website
😄 Have a wonderful day!

Posted on Apr 15 by:

Discussion

markdown guide
 

I'd be interested to see the difference in execution time on large data sets in the different languages.

 

Woah! How on earth did I forget that. Will do this soon. Thanks 😄