This is an old revision of the document!

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 barcodes. I find the whole process interesting. This is because sorting algorithm is an essential part of computer science curriculum ¹⁾. I do have some special connection with sorting algorithm - I bumped into Sir Charles Antony Richard Hoare FRS FREng ²⁾³⁾ the day before I was formally taught quicksort ⁴⁾ for the second time ¹⁾ in 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 ⁵⁾. However some of the concepts in algorithm analysis can still be applied to physical world, for example time complexity and space complexity ⁶⁾.

In this blog post, we explore the way Parkrun volunteers sort barcodes, using concepts from computer science.

Bucket sort

Parkrun uses a physical implementation of bucket sort ⁷⁾⁸⁾. This is illustrated by the following two pictures taken at Parkrun.

Bucket sort has a

¹⁾ https://en.wikipedia.org/wiki/Sorting_algorithm#History

²⁾ https://en.wikipedia.org/wiki/Tony_Hoare

³⁾ https://www.fangfufu.co.uk/wiki/doku.php?id=public:bumping_into_sir_tony_hoare_on_the_day_before_i_learnt_quicksort

⁴⁾ https://en.wikipedia.org/wiki/Quicksort

⁵⁾ https://en.wikipedia.org/wiki/Analysis_of_algorithms#Cost_models

⁶⁾ https://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html

⁷⁾ https://en.wikipedia.org/wiki/Bucket_sort

⁸⁾ https://www.oreilly.com/library/view/algorithms-in-a/9780596516246/ch04s08.html

¹⁾

I was taught it once in A-Level Maths D1 module when I was a Year 12 student in Ashmole School, London.