CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | CS@Williams

Lab 5: Sorting

This lab is about getting practice with merge sort and Comparators.

Obtaining the Starter Code

Open your terminal using Control-` (this is a backtick, not an apostrophe: the key is above your Tab key). Type git pull and then hit enter.

Once you have run the git pull command, use VSCode to open the Lab05 folder in your repo. (Remember to use Open Folder, and not Open File.) You should see: ByLatitude.java ByName.java ByPopulation.java City.java IntComparator.java SortCities.java cities.txt

Task 0: Looking Over the City Class and Comparator

We'll be sorting lists of cities in this lab. Let's quickly look at the City class. It has a constructor which takes in a single String; we won't be using that. We'll only be using the getter method for the instance variables.

Now, let's look at the ByPopulation comparator. It has a single compare method that takes in two cities, and gives a return value based on which is smaller by population.

We'll be sorting the cities in cities.txt. This file contains information on all cities in the world with a population of more than 15000. (There is a Williamstown in the set, but unfortunately it's Williamstown, NJ.)

Task 1: Implementing Merge

Fill in the merge method in SortCities.java. (Note that while we will eventually be sorting cities, this method should work to merge any two arrays of generic type.) Your method should copy the elements from firstHalf and secondHalf into cities, overwriting any elements in cities. (You'll use the set method to do this.)

Write a simple test in the main() method: create two sorted arraylists of integers, and print the result of merging them. Use a comparator of type IntComparator for this test. (Doing this test is required; be sure to submit it with your lab.)

Task 2: Implement Merge Sort

Fill in the mergeSort method in SortCities.java. Again, this method should work for any type E.

Write a simple test in the main() method: create an arraylist of integers, and print the result of merge sorting it. Use a comparator of type IntComparator for this test. (Doing this test is required; be sure to submit it with your lab.)

Task 3: Sort Cities by Population

Using your mergeSort method and the ByPopulation comparator, sort the cities by population in the main() method. (The cities are already in an ArrayList called cities, and the print statements are already there; you only need to create the comparator and call the sort.)

Task 4: Sort Cities by Name

First, fill in the ByName class to sort cities by name. Then, fill in the main() method to sort the cities by name. You do not need to create the ArrayList of cities, fill it in, or print it: you only need to create the comparator and call sort.

Task 5: Sort Cities by Latitude

First, fill in the ByLatitude class to sort cities by latitude. Then, fill in the main() method to sort the cities by latitude. You do not need to create the ArrayList of cities, fill it in, or print it: you only need to create the comparator and call sort.

Task 6: Submit

Submit your code to Gradescope (Lab 05). There is no autograder this week.

It's time to add, commit and push your file. Enter each of the following commands into your terminal one at a time. (The pdf instructions from Lab00 have more extensive instructions for how to do this.)

git add SortCities.java ByName.java ByLatitude.java
git commit -m "finished with lab 5"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab05, then SortCities.java, and make sure that you can see the modifications you made. If you can see the changes, you're all set! If you finish early, please talk to one of the instructors to make sure everything is in the right place before you leave.