Problem 🤔

Implement the merge sort algorithm.

Real World Applications 🌎

Merge sort is often used in database scenarios, because often we store data in different files and need to merge them. It’s also useful in distributed systems where data needs to be merged from multiple source. A great use case could be mapReduce!

Also, you probably merge every morning at work when you pull the latest code!

The Finer Details 🔎

Another nice recurisve sorting algorithm!

Solution 💡

Complexity Analysis 🧮

Time Complexity

O(n*log(n))

Space Complexity

O(n)

Recurisve depth of stack is O(log(n)). We use helper lists (L + R) that store all elements in our list for O(n).

Takeaways 🎉🥳

• In merge sort remember to place the last elements in the array! See the last 2 while loops!