The sorting problem is one of the oldest programming tasks that an engineer deals with. We have a set of records and we know that we want to find a specific one sometime later, and we want to find that one fast. To find it, we sort the records in a specific order that helps us find the record we want quickly.

As an example, we have the names of students with their marks on some cards. When students come to the office asking for their results, we look through all of the cards one after the other to find the name of the enquiring student. However, it is better if we sort the cards by the names of the students alphabetically. When a student makes an enquiry, we can search the mark attached to the name much faster.

We can look at the middle card; if it shows the name of the student, then we are happy to have found the name and the mark. If the card precedes the name of the student alphabetically, then we will continue searching in the second half; otherwise, we will...