History of Sorting Algorithms

The story behind an invention/discovery is always fascinating. Be it Newton having an apple fall on his head, or serendipitous happenings which led to discoveries like Penicillin, Radioactivity, etc - there is always something intriguing about stories of such a kind. Often, many inventions/discoveries either do not have such a story or they have a story and it is not well known.

In this post, I would like to share with you the history of how various sorting algorithms were developed.
(1) Selection Sort - Invented by Mr. Selection
(2) Bubble Sort - Invented by Mr. Bubble
(3) Merge Sort - Invented by Mr. Merge
(4) Counting Sort - Invented by Mr. Count

Story of Selection Sort:-
Mr. Selection's mother was an English teacher. Once every 3 months, she bought home examination papers to evaluate. Once the valuation was complete, she liked the papers arranged highest marks first and lowest last. She had a practice to praise the highest while handing out the paper, and at the same time, rebuke the person who scored the least. Having the highest scorer's sheet handed out first ensured that everyone got to know who he/she was; it would be correct kind of boost required for the student. Also, having the person who scored least to be called out last would help because by then, everyone else would have got their papers and would be busy with their own sheets, so least attention is drawn to it.

His mother gave him the task of arranging the papers. He decided to follow this strategy to arrange the papers.
(1) Place all the sheets side-by-side.
(2) Scan from left to right and find out the guy who got the highest.
(3) Take his sheet and place it face-down on another table.
(4) Among the leftover papers, scan again from left to right and find out the highest in the remaining set.
(5) Place his paper too, face-down, on the paper already placed on the table.
Repeat (4) and (5) until the entire set is complete.

10 years later, when he had to write a program to sort values, he recalled arranging the papers. He realised that in every pass, he selected the maximum and then placed it aside. He did the same thing in the program and named the algorithm after himself :)
Story of Bubble Sort:-
Mr. Bubble was a student of Pineapple High School Convent. During the daily prayers, all students of the same class stood together in a line and it was required that the students stood in ascending order of their heights. During the first ever time the students had to make a line, there was utter chaos. Everyone was shouting... "hey you are shorter than me, come and stand in front of me", "hey lambu, go and stand behind re", etc... The teacher called for silence!!! She thought of a way to arrange all of them.

The first sorting process that struck her was to find the shortest one and place him first; find the next shortest one and place him second and so on... She realised that the process of finding the shortest student among a set of students was very tricky. When she scanned from the top to the bottom of the line often she would not be able to decide whether a guy near the end was shorter than a guy she saw in the beginning. She could only decide who was shorter if they stood beside each other. So she went to the head of the line. She started swapping two adjacent students if they were not in order. She realised that after the first pass, clearly the tallest guy was at the end. She then decided to do the same to the remaining set. She kept performing the same and soon the line was sorted.

Mr. Bubble was impressed with what his teacher did. This incident was etched in his mind. Years later, he read a paper authored by Mr. Selection about a sorting algorithm called selection sort. He somehow happened to recall his teacher's method of sorting and realised it was different from the selection sort. He realised how the teacher bubbled the elements to the ends of the array. He decided to try programming it. He programmed it and it worked. This was how the Bubble Sort was born!!!

Story of Merge Sort:-
Mr. Merge was a scientist working in basketball research laboratories. The lab was far away from his home and so he chose to rent a place closeby. While shifting, he packed all his books into small cartons. He was an avid reader, because of which there were a really high number of cartons.

Once he reached, he wanted to take out the books and arrange them on his shelf in order of their heights. He realised that opening all the cartons and then sorting the books would make too much of a mess. He decided that he would break his problem into smaller bits. He first opened the cartons and arranged the books in the carton according to height. This was not much of a problem because the cartons could not hold too many books. Once arranged, he merged the cartons. He realised that having already sorted them made his job a bit easier. Merging small sorted sets of elements to get one full big sorted set was easier than sorting the entire large set together!!! The next thing you know - Merge Sort was born!!!

Story of Counting Sort:-
Mr. Count's little brother studied at samsung kindergarten school. Count would go to pick his brother up every afternoon. One afternoon, he was a bit early, and he could overhear what was going on in his brother's class. The teacher had listed a huge array of alphabets (randomnly and with repetition). Each kid was asked to sort the list. The teacher believed that this exercise would help kids get familiar with the alphabets as well as develop their memory (for a human to sort a list, it does require a little bit of memory usage on his part). Mr. Count's little brother could not do the exercise. The bell rung and before the teacher dismissed the class, he told Count's brother - "I will not send you home tomorrow if you do not complete this exercise in front of me".

Mr. Count then started wondering how he could make his little brother's job easy. The real problem for the kid was that there were too many alphabets on the board. The kid indeed knew the order of the alphabets when he was asked to chant it - "abcdefghijklmnop...". But to re-arrange them when they were in random fashion was a little difficult for the kid. Everytime, he had to recite the alphabet in his head. This was taking a lot of time.

Mr. Count then came up with a strategy:-
(1) He asked his brother to make a table with two colums and 26 rows
(2) In the first column, write down numbers alphabets from a to z
(3) Now, start scanning the array left-right and as you encounter each alphabet, put a line against the corresponding letter in the table. Once done, forget about the array.
(4) Now just scan the table from top to bottom. The number of times each letter had to be listed was obviously determined by the number of dashes for that particular alphabet.
(5) Hence, a top to bottom scan; with simultaneous listing of the alphabet would give the sorted list the teacher wanted.

Count's brother caught on with this idea and could complete the exercise next day with significant ease. The brother excitedly mentioned to count that the teacher was particularly impressed about the speed with which he completed the task.

When count was a university student, he had to write a program to sort a similar kind of list. The range of values was limited and known. There were no memory constraints and the process of sorting had to be as fast as possible. It goes withough saying that this was the birth of the counting sort.

Things to notice:-
(1) Mr. Merge had the same problem of sorting a large number of items and that too as efficiently as possible. A Merge sort is indeed used in that kind of a situation.
(2) Mr. Count had a "limited range of values". That is indeed the kind of situation a counting sort is used in!
(3) Both Mr. Selection and Mr. Bubble did not have too many things to handle at the same time. Selection and Bubble Sort are used for small arrays!

It goes without saying that these stories are pure crap. They are just things I made up to satisfy myself. However, I somehow feel the real stories could not have been much different; maybe different situations and also the scientists' parents being a little more creative in naming their children :P.

This is not an attempt from me to trivialise any matter. I have a feeling that making up stories like this for everything new you learn aids your understanding. I try and do it for everything I learn and I find that it really helps me.

Another thing I would like to point out to people. Successful computer scientists are not people who sit in front of the computer all day. They are people who observe everything around them and find inspiration to translate human language into a language the computer can understand. Edsger Dijkstra once said "...computer science is no more about computers than astronomy is about telescopes...". Often I hear dialogues like "...I don't want to get into computer science because I hate sitting in front of the computer all day man...". I hope this post shows those people that computer science does not need you to stare at the screen all the time; studying computer science does not mean you will spend a life building meticulous GUIs for Grocery Applications at Infosys! There is a difference between the terms Information Technology and Computer Science. Please do not use them interchangeably!!! Computer Science is as evergreen a science as any other. Booms and busts in IT have no effect on the science and its sacredness. This realization does not dawn easily on computer engineers even, let alone the others. I just wish that people did not have this misconception.

Abhiram.