#### Return to Index

#### MP3: Restaurant View Revisited : `12/01/2021`

#### MP3: Restaurant Graphs and Hashing : `11/30/2021`

#### MP3: Practical Sorting : `11/29/2021`

#### Implementing a Map : `11/19/2021`

#### Hashing : `11/18/2021`

#### Binary Search : `11/17/2021`

#### MP2: Related Restaurants : `11/16/2021`

#### MP2: Restaurant Activity : `11/15/2021`

#### Quicksort : `11/12/2021`

#### Merge Sort : `11/11/2021`

#### Sorting Algorithms : `11/10/2021`

#### MP2: Client-Server Communication : `11/09/2021`

#### MP2: CSV to JSON : `11/08/2021`

#### Graph Algorithms : `11/05/2021`

#### Graphs : `11/04/2021`

#### Practice with Recursion : `11/03/2021`

#### MP1: Search and Callbacks : `11/02/2021`

#### MP1: Views and UI : `11/01/2021`

#### Trees and Recursion : `10/29/2021`

#### Trees : `10/28/2021`

#### Recursion : `10/27/2021`

#### MP1: Serialization and Searching : `10/26/2021`

#### MP1: Serialization and Sorting : `10/25/2021`

#### Lists Review and Performance : `10/22/2021`

#### Linked Lists : `10/21/2021`

#### Algorithms and Lists : `10/20/2021`

#### Continuing MP0 : `10/19/2021`

#### Getting Started with MP0 : `10/18/2021`

#### Lambda Expressions : `10/15/2021`

#### Anonymous Classes : `10/14/2021`

#### Practice with Interfaces : `10/13/2021`

#### Implementing Interfaces : `10/12/2021`

#### Using Interfaces : `10/11/2021`

#### Working with Exceptions : `10/08/2021`

#### Throwing Exceptions : `10/07/2021`

#### Catching Exceptions : `10/06/2021`

#### References and Polymorphism : `10/05/2021`

#### References : `10/04/2021`

#### Data Modeling 2 : `10/01/2021`

#### Equality and Object Copying : `09/30/2021`

#### Polymorphism : `09/29/2021`

#### Inheritance : `09/28/2021`

#### Data Modeling 1 : `09/27/2021`

#### Companion Objects : `09/24/2021`

#### Encapsulation : `09/23/2021`

#### Constructors : `09/22/2021`

#### Objects, Continued : `09/21/2021`

#### Introduction to Objects : `09/20/2021`

#### Compilation and Immutability : `09/17/2021`

#### Maps and Sets : `09/16/2021`

#### Lists and Type Parameters : `09/15/2021`

#### Imports and Libraries : `09/14/2021`

#### Multidimensional Arrays : `09/13/2021`

#### null : `09/10/2021`

#### Algorithms and Strings : `09/09/2021`

#### Strings : `09/08/2021`

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

#### Errors and Debugging : `09/03/2021`

#### Functions : `09/02/2021`

#### Algorithms I : `09/01/2021`

#### Loops : `08/31/2021`

#### Arrays : `08/30/2021`

#### Compound Conditionals : `08/27/2021`

#### Conditional Expressions and Statements : `08/26/2021`

#### Operations on Variables : `08/25/2021`

#### Variables and Types : `08/24/2021`

#### Welcome to CS 124 : `08/23/2021`

# Merge Sort

Kotlin

Created By: Geoffrey Challen

/ Updated: `2021-11-05`

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 today 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!

### Solution Walkthrough

Interactive Walkthrough

Click on an icon below to start!