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

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?

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

Need more practice? Head over to the practice page.