Exercise: Sort the Music Library

A music app's library view takes a minute to sort 50,000 imported songs, and tied songs swap places between refreshes: write the comparison, a hand-written sort that's fast and keeps ties in order, and the built-in sort to check it against, and let the tests check them, ties and the 50,000 songs included.

Journeyman · Data Structures · Updated

By

Here's the ticket from the music app's library team:

The library view lists songs by artist, then album, then track number. People import 50,000 songs at once, and today's sort, which compares the songs one by one, leaves them staring at a spinner for a minute or more. And when two copies of a song tie on all three, such as a live Slow Rain and the album one, they swap places between refreshes.

  1. The library's order: by artist, then album, then track number, with names compared letter by letter, capitals first.
  2. 50,000 songs are sorted in under 2 seconds.
  3. Songs that tie on all three keep the order they were imported in, every time.
  4. We're moving to the language's built-in sort, and we want a hand-written sort to check it against. Both have to give the same order, ties included.

This chapter has given you every piece. The tests check the comparison, the order of an eight-song library, ties in both sorts, 1,000 songs sorted both ways, and then the ticket's import: 50,000 songs in under 2 seconds.

Before you start

You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.

Get the exercise code

Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-sort-music-library, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

git clone https://github.com/ask-codey/exercise-ds-sort-music-library.git

Git makes a folder, exercise-ds-sort-music-library, with the exercise code inside.

The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:

  • your code: one file with three functions to finish (the repository's README.md names the file for each language);
  • a song: an artist, an album, a track number and a title, as a Song record in C# and Java, a Song dataclass in Python, and an object like { artist: "Night Bus Trio", album: "City Lights", track: 2, title: "Blue Hour" } in JavaScript and TypeScript;
  • the tests that check your functions. You don't need to change them;
  • a demo program that sorts an eight-song library both ways.

In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.

What to do

Every function is already there, with its parameters, and returns 0 or an empty list for now. The comment above each one says what it should return. Here is the first one in Python, as the starter has it (the other languages say the same in their own syntax):

def compare_songs(a, b):
    """
    Compare two songs the way a music library lists them: by artist,
    then by album when the artists are the same, then by track number
    when the albums are the same too. Give back a negative number when a
    comes first, a positive number when b comes first, and 0 when they
    tie on all three. Compare names letter by letter, capitals first.

    compare_songs(Copper Kettle Band / Kettle Songs / 1, Night Bus Trio / Afterglow / 4) -> negative
    compare_songs(Night Bus Trio / City Lights / 2, Night Bus Trio / City Lights / 1) -> positive
    compare_songs(Night Bus Trio / City Lights / 2, Night Bus Trio / City Lights / 2) -> 0
    """
    return 0
  1. Compare two songs. Finish compareSongs (compare_songs in Python, CompareSongs in C#): artist first, then album, then track number.
  2. The hand-written sort. Finish mergeSort, using compareSongs to decide which song comes first. It has to sort 50,000 songs in under 2 seconds and keep songs that tie in the order they came in.
  3. The built-in sort. Finish builtInSort with your language's built-in sort and compareSongs, ties kept in order too.
  4. Name the growth rates. On each sort's Growth rate: line, write its Big-O and a few words on why.

Check your work

Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).

Language Run the tests Run the demo
C# dotnet test dotnet run --project MusicLibrary
Java ./mvnw test (.\mvnw test in PowerShell) java src/main/java/Demo.java
Python python -m pytest python demo.py
JavaScript npm test node demo.js
TypeScript npm test node demo.ts

At first all 10 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: on City Lights, track 2 comes after track 1.

<details> <summary>Stuck?</summary>

  • Where to look: the hand-written sort is the one from A Million Songs to Sort Before Bedtime: Merge Sort, and keeping ties in order is Most Played, Then A to Z: Stable and Built-In Sorts.
  • Compare one key at a time. If the artists differ, they decide. Only when they're the same do the albums decide, and only when those are the same too does the track number.
  • Names compare letter by letter, capitals first: string.CompareOrdinal in C#, compareTo in Java, < in Python, JavaScript and TypeScript. Track numbers are numbers: subtracting one from the other gives a negative, zero or positive answer.
  • Your merge sort is the lesson's, with compareSongs(left, right) <= 0 in place of left <= right. The <= is what makes it stable: one test gives it two versions of Slow Rain that tie on all three keys, and they must stay in the order they came in.
  • The built-in sort takes your comparison. In C#, use LINQ's OrderBy with your comparison, not List<T>.Sort, which can shuffle songs that tie. Python's sorted wants a key instead, so the starter imports cmp_to_key, which turns a comparison into a key.
  • Give back new lists, and leave the library you were given in its own order.

</details>

When you're done

Every test is green, and the demo prints the same ten lines in every language:

Merge sort:
Copper Kettle Band / Kettle Songs / 1: Echo Park
Copper Kettle Band / Kettle Songs / 3: Falling Up
Marigold Avenue / Lantern Season / 2: Lemon Skies
Marigold Avenue / Sunday Static / 1: Amber Road
Marigold Avenue / Sunday Static / 2: Copper Moon
Night Bus Trio / Afterglow / 4: Velvet Train
Night Bus Trio / City Lights / 1: Desert Lights
Night Bus Trio / City Lights / 2: Blue Hour
Built-in sort gives the same order: yes

Your merge sort and the built-in sort agree, and both are O(n log n), the speed limit from Can Any Sort Go Faster? The n log n Speed Limit. Which one would you put in a real app, and why?

<details> <summary>Why Should I Choose This?</summary>

The ticket's import is 50,000 songs. A sort that compares song by song, like today's, makes hundreds of millions of comparisons: measured as an insertion sort, it took 8.8 seconds in TypeScript, 14.9 in C#, 28.5 in Java and over 2 minutes in Python. A quicksort would be fast, but the in-place one can swap a song past its twin, which breaks the ticket's third line. Merge sort makes about 800,000 comparisons, took a fraction of a second in every language (0.15 seconds in Python), has no bad day, and takes from the left pile on a tie, so the two Slow Rains keep their import order. In a real app you'd use the built-in sort, as long as it's a stable one: Java's, Python's and JavaScript's are, and in C# that means OrderBy, not List<T>.Sort. What merge sort gives up is memory: a second copy of the list while it merges.

</details>

Where else does this shape show up?

You've used "split it in half, sort each half, then merge two sorted piles". Before you open the answers, think of three other places, at work or in daily life, where a big job is split, each part is done on its own, and the results are combined, or where two sorted piles become one.

<details> <summary>Some answers</summary>

  • Two teachers merging their sorted piles of exams into one class list, always taking the top exam that comes first.
  • Combining two sorted bank statements, or two phones' contact lists after switching phones.
  • Sorting a file too big for memory: sort it in chunks that fit, then merge the sorted chunks, which is how databases sort huge tables.
  • A tournament bracket, where each half of the draw is played out on its own and the winners meet.
  • A big team splitting a job in halves and quarters, and putting the pieces back together.

</details>

Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

  1. On GitHub, click +, then New repository. Name it (for example exercise-ds-sort-music-library), choose Public, and click Create repository. Leave out the README: your folder already has one.

  2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

    git remote set-url origin https://github.com/your-name/exercise-ds-sort-music-library.git
    git add .
    git commit -m "My solution"
    git push -u origin main
    
  3. Paste your repo's address, such as https://github.com/your-name/exercise-ds-sort-music-library, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

So what

You've now searched and sorted the way real apps do: sorted data, found by halving, put in order by a stable O(n log n) sort. Sorting is the price the halving search pays for its O(log n) look-ups.

What Module 5 unlocks

Sorted lists made searching fast, but you've now felt their price twice: every new item slides the others along to keep the order, and every search still takes about 20 looks. Module 5, Fast Lookup, starts at a concert's coat check, where the paper tickets have run out and 3,000 coats arrive in a rush. A rack kept A to Z makes every new coat slide the rest along. What if the guest's name itself told you which hook to go to, so finding took one step, with no sorting at all? That's a hash table, the structure behind every dictionary, cache and "have I seen this before?" check, and you'll build one yourself.

Key terms

Related