# 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).

Interactive Walkthrough

Click on an icon below to start!

## 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.