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

# Merge Sort

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?

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: learncs.online Staff

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

Please Log In to Complete Homework Problems

## More Practice

Need more practice? Head over to the practice page.