Kotlin
Java

Merge Sort
Java

Created By: Geoffrey Challen
/ Updated: 2022-05-23

This lesson continues our exploration of sorting by examining a new approach. We'll start with a simple but powerful observation, and then examine how to build on it to create a complete sorting algorithm. This will also represent our first sorting algorithm that achieves best-case sorting performance! What are we waiting for?

merge

We'll begin with an observation.

Use a diagram to explain how it is straightforward to merge two already sorted arrays. This explanation should be language agnostic!

Next, let's implement merge on two int arrays and confirm our hunch about its performance.

Implement merge and demonstrate that it is O(n).

Mergesort

Next let's consider how to design a sorting algorithm that utilize our merge method. We'll also use this as a chance to point out how we can apply recursive algorithms on arrays, rather than trees, which we've used in the past.

Demonstrate how array recursion works and apply it to Mergesort. This explanation should be language agnostic!

Finally, let's analyze the performance of Mergesort. This is an interesting case! Let's walk through it carefully.

Analyze the performance of Mergesort and show how it is O(n log n). Point out that this is the best worst-case performance of any sorting algorithm. And that Mergesort has no input dependence. This explanation should be language agnostic!

Show how to complete the homework problem above. Feel free to cover multiple approaches!

More Practice

Need more practice? Head over to the practice page.