« Back to projects

Merge-sort with prompts for non-numeric data

Most sorting algorithms seem to be based on the idea that each node of data to be sorted has a numerical value associated with it. This, of course, is not always a case.

I had just signed up to the site YMDb.com, which allowed users to put up a list of their top twenty favourite films. Being a meek individual, and daunted by the prospect of having to arrange my video library into some kind of order, I decided I needed some assistance.

Details

I took a look on Wikipedia for sorting algorithms, and looked through the most common ones. A lot of them were supposedly quite efficient on large amounts of data, and even small amounts, but I found that a lot of the algorithms might end up comparing two bits of data twice.

I needed an algorithm that only compared two items (films in my case) once, and additionally that the sorting algorithm only relied on a simple "greater than" or "less than" comparison, since it wouldn't be sensible for me to first go through my film collection and assign an arbitrary number to each film; I just wanted to be asked, "Is FILM1 better than FILM2?" lots of times.

I settled on Merge Sort, which seemed to work in a sensible way, and wrote a quick script in Python to do this. It divides a data set up into two groups based on whether each item was greater than or less than the middle item in the group, then sorts those subsets in the same fashion until there are only two items in each subgroup. This was ideal since the comparison could be in the form of a simple question to the user; me! And I like simple questions.

Examples

$ python mergesort.py Usage: mergesort.py <item1> <item2> <item3> ... $ python mergesort.py "Star Wars" "Terminator" "Back to the Future" *** MERGESORT by Nick Murdoch, 2006 *** Type 1 if you prefer the first film given, or 2 if you prefer the second. Terminator or Star Wars? 2 Terminator or Back to the Future? 1 1: Star Wars 2: Terminator 3: Back to the Future

Installation

Download the source code below. (Install Python, if you're on Windows.) Run python mergesort.py "item1" "item2" ....

Download