This is an old revision of the document!
Table of Contents
How Parkrun volunteers sort barcodes - a computer scientist's perspective
On the Christmas day of 2018, I volunteered at Norwich Parkrun. Towards the end, I ended up helping out with sorting the plastic barcodes. I find the whole process interesting. This is because sorting algorithm is an essential part of computer science curriculum 1). I do have a special connection to sorting algorithm - I bumped into Sir Charles Antony Richard Hoare FRS FREng 2)3), the inventor of quicksort algorithm 4), the day before I was formally taught quicksort for the second time 1) as a computer science undergrad in University of York.
Sorting numbers inside a computer is a bit different to sorting objects in physical world. This is mainly because the uniform cost model does not apply in the physical world 5). However some of the concepts in algorithm analysis can still be applied to physical world, for example time complexity and space complexity 6).
In this blog post, we analyse the algorithm which Parkrun volunteers use to sort barcodes, using some concepts from computer science.
Bucket sort
Parkrun uses a physical implementation of bucket sort 7)8). This is illustrated by the following two pictures taken at Parkrun.
Bucket sort is a distribution sort - the original input is split into multiple substructure, where comparison sort is performed. It is effectively a two-stage sorting algorithm, how it works can be summarised in the following four steps:
- Initialise the empty buckets.
- Put each object into their corresponding bucket.
- Sort each non-empty bucket using a comparison sort algorithm.
- Visit the buckets in order and put all elements back into the original array.
On computers, bucket sort has the following properties:
- average time complexity $O(n+\frac{n^2}{k}+k)$,
- worst case time complexity: $O(n^2)$,
- worst case space complexity: $O(n \cdot k)$,
where $k$ is the number of buckets.
In Parkrun's particular implementation, the total number of buckets is not defined. Instead, each bucket is set to hold 25 barcodes. The total number of buckets depends on the amount of plastic barcodes.
Cost models
When we analyse algorithms on a computer, we use a 9),