ProjectsSort Tool
A command-line program that sorts the lines of a file like the Unix sort tool, drops repeated lines with -u, lets you choose the sorting algorithm, and can put lines in a random order while keeping identical ones together. Building several algorithms behind one interface teaches what sorting really costs, why stability and the choice between byte order and a language's alphabetical order change the output, and how a real sort copes with files bigger than memory.
From Coding Challenges #6 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 8 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Step 1 has to sort every word of a whole book, and step 3 asks you to compare algorithms, which only makes sense once you can say what each one costs as the input grows.
Covers: the comparison model · the n log n limit · quadratic sorts and where they break · best, average and worst case · the cost of comparing two lines · extra memory
Comparison sort (Wikipedia) ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 2.1 Elementary Sorts ↗ · Sorting algorithm (Wikipedia) ↗
Step 3 names these algorithms and asks how each one works with -u, and the word list is full of repeated words, the input that hurts a careless quicksort.
Covers: splitting and merging · partitioning and the choice of pivot · many equal keys and three-way partitioning · the heap kept inside the array · stability · hybrid sorts
Algorithms, 4th edition (Sedgewick and Wayne): 2.2 Mergesort ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 2.3 Quicksort ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 2.4 Priority Queues and heapsort ↗
Step 3 lists radix sort next to the comparison sorts, and it shows where the n log n limit comes from and why it only binds sorts that compare.
Covers: dealing lines into buckets by one byte · most significant byte first for text · last byte first for fixed-width keys · shorter lines before longer ones · when it beats comparison sorts
Radix sort (Wikipedia) ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 5.1 String Sorts ↗ · FreeBSD manual: sort(1) ↗
Step 1 asks for lexicographic order, and the page's first words are all in capitals, which is byte order. To compare your output with the real sort you have to run it with LC_ALL=C.
Covers: lexicographic order · byte order and LC_ALL=C · the locale's collation rules · case, accents and punctuation · sort keys
GNU coreutils FAQ: Sort does not sort in normal order! ↗ · Unicode Technical Standard #10: Unicode Collation Algorithm ↗ · GNU coreutils manual: sort invocation ↗
Step 2 adds -u and asks whether to remove duplicates before, during or after sorting, and step 3 asks how each algorithm works with it. The BSD sort won't use quicksort or heapsort with -u, because there -u implies a stable sort.
Covers: neighbours after sorting · dropping copies inside the merge or the partition · a hash set before sorting · what counts as equal · which copy is kept
GNU coreutils manual: uniq invocation ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 3.4 Hash Tables ↗ · FreeBSD manual: sort(1) ↗
The page's word list fits in memory easily, but the real sort handles files of any size, and this is where it differs most from a textbook sort.
Covers: why sort must read everything first · sorted runs in temporary files · merging many runs with a heap · buffer size and merge passes
External sorting (Wikipedia) ↗ · GNU coreutils manual: sort invocation ↗
Step 4 asks for -R, a random order where identical lines stay together, and combined with -u the output must still change from run to run.
Covers: shuffling versus random sort · sorting by a random hash of each line · seeding and repeating a run · breaking ties between different lines · an unbiased shuffle
GNU coreutils manual: sort invocation (see --random-sort) ↗ · Fisher–Yates shuffle (Wikipedia) ↗ · Universal hashing (Wikipedia) ↗
Step 3 gives no expected output and suggests unit tests, every algorithm must print the same thing, and step 4's output changes on every run.
Covers: in order and a permutation of the input · comparing against the real sort · inputs that break sorts · testing output that is random
Differential testing (Wikipedia) ↗ · What is property based testing? (Hypothesis) ↗
What you'll build · 5 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project, download the book the page links, and turn it into a word list with one word per line using the page's tr and sed recipe. Make sure the real sort is available to compare against.
Works whenThe word list has one word per line and no line starts with a digit. The real sort, run on it with LC_ALL=C, gives you output to compare yours with.
Given a file name, read all of its lines and print them in lexicographic order, comparing lines byte by byte.
Works whenUnder LC_ALL=C the output is the same as the real sort's, line for line, repeats included. Piped through uniq, the first words start with a capital A, because in byte order every capital letter comes before every lowercase one.
Concepts: comparison sorting and what it costs · byte order versus collation · sorting data larger than memory
With -u, print each distinct line only once. Decide whether to remove duplicates before, during or after sorting, weighing time, memory and how easily the choice extends to later options.
Works whenThe output with -u is the same as your sorted output piped through uniq, and the same as the real sort -u under LC_ALL=C, so its first five lines match step 1's.
Concepts: removing duplicates
Let the user choose which algorithm sorts the lines, with options named like the BSD sort's: --radixsort, --mergesort, --qsort and --heapsort. Build as many of them as you like, and decide how each one works with -u.
Works whenThe page gives no expected output, so your tests are the check. Every algorithm prints exactly the same output as the others and as the real sort under LC_ALL=C, with and without -u, on the word list and on small inputs: an empty file, one line, all lines equal, already sorted and reversed.
Concepts: comparison sorting and what it costs · merge sort, quicksort and heapsort · radix sort · removing duplicates · what makes a sort correct, and how to test it
With -R or --random-sort, print the lines in a random order that changes on every run, keeping identical lines next to each other. It must also work together with -u.
Works whenTwo runs with --random-sort and -u print the same lines as -u alone, in different orders. Without -u, all copies of a word sit next to each other.
Concepts: random order that keeps equal lines together · what makes a sort correct, and how to test it