#### Implementing a Map : `12/05/2022`

#### Streams : `12/02/2022`

#### Generics : `12/01/2022`

#### Hashing : `11/30/2022`

#### Binary Search : `11/29/2022`

#### MP3: Getting Started : `11/28/2022`

#### Quicksort : `11/18/2022`

#### Merge Sort : `11/17/2022`

#### Sorting Algorithms : `11/16/2022`

#### MP2: Add Place Activity : `11/15/2022`

#### MP Debugging Part 1 : `11/14/2022`

#### MP2: Launching An Activity : `11/11/2022`

#### Practice with Recursion : `11/10/2022`

#### MP2: Server Add Place : `11/09/2022`

#### Trees and Recursion : `11/07/2022`

#### Trees : `11/04/2022`

#### Recursion : `11/03/2022`

#### MP Debugging Part 0 : `11/02/2022`

#### MP1: Search : `11/01/2022`

#### MP1: Serialization and Data Loading : `10/31/2022`

#### Lists Review and Performance : `10/28/2022`

#### Linked Lists : `10/27/2022`

#### Algorithms and Lists : `10/26/2022`

#### Continuing MP0 : `10/25/2022`

#### Getting Started with MP0 : `10/24/2022`

#### Lambda Expressions : `10/21/2022`

#### Anonymous Classes : `10/20/2022`

#### Practice with Interfaces : `10/19/2022`

#### Implementing Interfaces : `10/18/2022`

#### Using Interfaces : `10/17/2022`

#### Working with Exceptions : `10/14/2022`

#### Throwing Exceptions : `10/13/2022`

#### Catching Exceptions : `10/12/2022`

#### References and Polymorphism : `10/11/2022`

#### References : `10/10/2022`

#### Data Modeling 2 : `10/07/2022`

#### Equality and Object Copying : `10/06/2022`

#### Polymorphism : `10/05/2022`

#### Inheritance : `10/04/2022`

#### Data Modeling 1 : `10/03/2022`

#### Static : `09/30/2022`

#### Encapsulation : `09/29/2022`

#### Constructors : `09/28/2022`

#### Objects, Continued : `09/27/2022`

#### Introduction to Objects : `09/26/2022`

#### Compilation and Type Inference : `09/23/2022`

#### Practice with Collections : `09/22/2022`

#### Maps and Sets : `09/21/2022`

#### Lists and Type Parameters : `09/20/2022`

#### Imports and Libraries : `09/19/2022`

#### Multidimensional Arrays : `09/16/2022`

#### Practice with Strings : `09/15/2022`

#### null : `09/14/2022`

#### Algorithms and Strings : `09/13/2022`

#### Strings : `09/12/2022`

#### Functions and Algorithms : `09/09/2022`

#### Practice with Functions : `09/08/2022`

#### More About Functions : `09/07/2022`

#### Errors and Debugging : `09/06/2022`

#### Functions : `09/02/2022`

#### Practice with Loops and Algorithms : `09/01/2022`

#### Algorithms : `08/31/2022`

#### Loops : `08/30/2022`

#### Arrays : `08/29/2022`

#### Compound Conditionals : `08/26/2022`

#### Conditional Expressions and Statements : `08/25/2022`

#### Operations on Variables : `08/24/2022`

#### Variables and Types : `08/23/2022`

#### Welcome to CS 124 : `08/22/2022`

# Merge Sort

Java

Created By: Geoffrey Challen

/ Updated: `2022-11-01`

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.