Kotlin

Java

#### 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`#### Static :

`28`#### Encapsulation :

`27`#### Constructors :

`26`#### Objects, Continued :

`25`#### Introduction to Objects :

`24`#### Compilation and Type Inference :

`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`

int[] merge(int[] first, int[] second) {

return null;

}

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`

`merge`

We’ll begin with an observation.

Next, let’s implement `merge`

on two `int`

arrays and confirm our hunch about its performance.

// Implement merge

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.

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

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 array of `int`

s and returns a sorted (ascending) array.
You should not modify the passed array.
If the array that is passed is `null`

you should throw an `IllegalArgumentException`

.

`Mergesort`

should extend `Merge`

, and its parent provides several helpful methods:

`int[] merge(int[] first, int[] second)`

: this merges two*sorted*arrays into a second sorted array. If either array is`null`

it throws an`IllegalArgumentException`

, so don't call it on`null`

arrays.`int[] copyOfRange(int[] original, int from, int to)`

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

Need more practice? Head over to the practice page.