#### Quicksort : `53`

#### Merge Sort : `52`

#### Sorting Algorithms : `51`

#### Practice with Recursion : `50`

#### Trees and Recursion : `49`

#### Trees : `48`

#### Recursion : `47`

#### Lists Review and Performance : `46`

#### Linked Lists : `45`

#### Algorithms and Lists : `44`

#### Lambda Expressions : `43`

#### Anonymous Classes : `42`

#### Practice with Interfaces : `41`

#### Implementing Interfaces : `40`

#### Using Interfaces : `39`

#### Working with Exceptions : `38`

#### Throwing Exceptions : `37`

#### Catching Exceptions : `36`

#### References and Polymorphism : `35`

#### References : `34`

#### Data Modeling 2 : `33`

#### Equality and Object Copying : `32`

#### Polymorphism : `31`

#### Inheritance : `30`

#### Data Modeling 1 : `29`

#### Companion Objects : `28`

#### Encapsulation : `27`

#### Constructors : `26`

#### Objects, Continued : `25`

#### Introduction to Objects : `24`

#### Compilation and Immutability : `23`

#### Practice with Collections : `22`

#### Maps and Sets : `21`

#### Lists and Type Parameters : `20`

#### Imports and Libraries : `19`

#### Multidimensional Arrays : `18`

#### Practice with Strings : `17`

#### null : `16`

#### Algorithms and Strings : `15`

#### Strings : `14`

#### Functions and Algorithms : `13`

#### Practice with Functions : `12`

#### More About Functions : `11`

#### Errors and Debugging : `10`

#### Functions : `9`

#### Practice with Loops and Algorithms : `8`

#### Algorithms I : `7`

#### Loops : `6`

#### Arrays : `5`

#### Compound Conditionals : `4`

#### Conditional Expressions and Statements : `3`

#### Operations on Variables : `2`

#### Variables and Types : `1`

#### Hello, world! : `0`

# Merge Sort

fun merge(first: Array<Int>, second: Array<Int>): Array<Int> {

return arrayOf<Int>()

}

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?

We’ll begin with an observation.

Next, let’s implement `merge`

on two `int`

arrays and confirm our hunch about its performance.

Interactive Walkthrough

Click on an icon below to start!

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.

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

## Homework: Mergesort

Created By: Geoffrey Challen

/ Version: `2020.11.0`

Create a public class named `Mergesort`

that provides a single *instance* method (this is required for testing)
named `mergesort`

. `mergesort`

accepts an `IntArray`

and returns a sorted (ascending) `IntArray`

. You should not
modify the passed array.

`Mergesort`

should extend `Merge`

, and its parent provides several helpful methods:

`fun merge(first: IntArray, second: IntArray): IntArray`

: this merges two *sorted* arrays into a second sorted
array.`fun copyOfRange(original: IntArray, from: Int, to: Int): IntArray`

: this acts as a wrapper on
`java.util.Arrays.copyOfRange`

, accepting the same arguments and using them in the same way.

(You can't use `java.util.Arrays`

in this problem for reasons that will become obvious if you inspect the rest of
the documentation...)

Note that you do need to use `merge`

and call it the correct number of times.
This will be tested during grading.
You should use an array of size 1 or 0 as your base case.

Please Log In to Complete Homework Problems

## More Practice

Need more practice? Head over to the practice page.