JavaImplementing a Map : 04/26/2024
map-reduce-filter : 04/25/2024
Generics : 04/24/2024
Hashing : 04/23/2024
Binary Search : 04/22/2024
MP3: Course Ratings : 04/19/2024
Quicksort : 04/18/2024
Merge Sort : 04/17/2024
Sorting Algorithms : 04/16/2024
MP Debugging Part 1 : 04/15/2024
MP2: Course Activity : 04/12/2024
Practice with Recursion : 04/11/2024
MP Debugging Part 0 : 04/10/2024
MP2: API Client : 04/09/2024
MP2: API Server : 04/08/2024
Trees and Recursion : 04/05/2024
Trees : 04/04/2024
Recursion : 04/03/2024
MP1: Filtering and Search : 04/02/2024
MP1: Loading and Sorting : 04/01/2024
Lists Review and Performance : 03/29/2024
Linked Lists : 03/28/2024
Algorithms and Lists : 03/27/2024
Continuing MP0 : 03/26/2024
Getting Started with MP0 : 03/25/2024
Lambda Expressions : 03/22/2024
Anonymous Classes : 03/21/2024
Practice with Interfaces : 03/20/2024
Implementing Interfaces : 03/19/2024
Using Interfaces : 03/18/2024
Working with Exceptions : 03/08/2024
Throwing Exceptions : 03/07/2024
Catching Exceptions : 03/06/2024
References and Polymorphism : 03/05/2024
References : 03/04/2024
Data Modeling 2 : 03/01/2024
Equality and Object Copying : 02/29/2024
Polymorphism : 02/28/2024
Inheritance : 02/27/2024
Data Modeling 1 : 02/26/2024
Companion Objects : 02/23/2024
Encapsulation : 02/22/2024
Constructors : 02/21/2024
Objects, Continued : 02/20/2024
Introduction to Objects : 02/19/2024
Compilation and Immutability : 02/16/2024
Practice with Collections : 02/15/2024
Maps and Sets : 02/14/2024
Lists and Type Parameters : 02/13/2024
Imports and Libraries : 02/12/2024
Multidimensional Arrays : 02/09/2024
Practice with Strings : 02/08/2024
null : 02/07/2024
Algorithms and Strings : 02/06/2024
Strings : 02/05/2024
Functions and Algorithms : 02/02/2024
Practice with Functions : 02/01/2024
More About Functions : 01/31/2024
Errors and Debugging : 01/30/2024
Functions : 01/29/2024
Practice with Loops and Algorithms : 01/26/2024
Algorithms : 01/25/2024
Loops : 01/24/2024
Arrays : 01/23/2024
Compound Conditionals : 01/22/2024
Conditional Expressions and Statements : 01/19/2024
Operations on Variables : 01/18/2024
Variables and Types : 01/17/2024
Welcome to CS 124 : 01/16/2024
Merge Sort
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?
mergemerge
mergeWe’ll begin with an observation.
Next, let’s implement merge on two int arrays and confirm our hunch about its performance.
MergesortMergesort
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
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 onjava.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.
More Practice
Need more practice? Head over to the practice page.