Algorithms and Data Structures in an Object-Oriented Framework (“ADSOOF”)

Sorting Arrays and ArrayLists: Part 2

Constructive Quicksort

Quicksort(1) on arrayLists can be programmed in a way very similar to the quicksort on Lisp lists we saw previously: we create two new empty arrayLists, then add all the elements of the original arrayList less than its first element to one of them, all the elements greater than or equal to the first element to the other, sort these two lists, and join the results together with the old first element in the middle. Here is the code for this: 

 public static ArrayList<Integer> sort(ArrayList<Integer> a)
 {
  if(a.size()<=0)
     return a;
  ArrayList<Integer> smaller = new ArrayList<Integer>();
  ArrayList<Integer> greater = new ArrayList<Integer>();
  Integer pivot = a.get(0);
  for(int i=1; i<a.size(); i++)
     {
      Integer n=a.get(i);
      if(n.compareTo(pivot)<0)
         smaller.add(n);
      else
         greater.add(n);
     }
  smaller=sort(smaller);
  greater=sort(greater);
  smaller.add(pivot);
  smaller.addAll(greater);
  return smaller;
 }
You can find this code in the files QuickSort1.java, QuickSort1a.java, QuickSort2.java from the code folder for this section. These differ only in the front end code provided, the code for the method sort is the same in each of them. There is a front end where you type in the numbers to be sorted, a front end where they are generated randomly and the result is displayed, and a front end where the numbers are generated randomly and the sorted arrayList is not displayed, just timing figures for how long it took to do the sorting. The front end which does not display the result can be used to test the sorting code with many more numbers than it would be sensible to print.

The code relies on arrayLists being flexible in size, since we do not know in advance the number of elements which are less than the first element. Note that the code uses a method from Java's ArrayList<E> class which has not been mentioned previously, addAll. If a and b refer to two arrayList objects, then the call a.addAll(b) destructively changes the object referred to by a so that all the elements from the object referred to by b are added to it, in the order they occurred, after the existing elements. You can see Java's official documentation for this method here.

If we wish to code constructive quicksort on arrays rather than arrayLists, we can do so simply as follows. Go through the original array once to find the number of elements less than the pivot. This gives us the size of the array of elements less than the pivot, and by implication, the size of the array of elements greater than or equal to the pivot not including the pivot itself. So we create arrays of these sizes and go back through the original array putting its elements into one or other of the new arrays. We then sort these new arrays, and join the results together in a final array of the same size as the original array. This gives us the following code: 

 public static Integer[] sort(Integer[] a)
 {
  if(a.length==0)
     return new Integer[0];
  else if(a.length==1)
     {
      Integer[] b = new Integer[1];
      b[0]=a[0];
      return b;
     }
  else
     {
      Integer pivot = a[0];
      int count=0;
      for(int i=0; i<a.length; i++)
         if(a[i].compareTo(pivot)<0)
            count++;
      Integer[] smaller = new Integer[count];
      Integer[] greater = new Integer[a.length-count-1];
      for(int i=1, j=0, k=0; i<a.length; i++)
         if(a[i].compareTo(pivot)<0)
            smaller[j++]=a[i];
         else
            greater[k++]=a[i];
      smaller = sort(smaller);
      greater = sort(greater);
      Integer[] b = new Integer[a.length];
      for(int i=0; i<count; i++)
         b[i]=smaller[i];
      b[count]=pivot;
      for(int i=0; i<greater.length; i++)
         b[count+i+1]=greater[i];
      return b;
     }
 }
Note the code for the loop which goes through the original array (referenced by variable name a) and copies references to its elements into either one or other of the new arrays (referenced by variable names smaller and greater). This is the loop: 
  for(int i=1, j=0, k=0; i<a.length; i++)
     if(a[i].compareTo(pivot)<0)
        smaller[j++]=a[i];
     else
        greater[k++]=a[i];
Here, i is the index to the original array, j is the index to the array smaller and k is the index to the array greater. These three int variables are declared together in the initialisation part of the loop, but only i is updated in the update part of the loop. This is because each time round the loop we need to consider the next element from the array a, but we only update j if we add that element to the array smaller and we only update k if we add that element to the array greater. Remember that j++ means “use the value of j then increase it by 1”. So smaller[j++]=a[i] is equivalent to: 
   smaller[j]=a[i];
   j=j+1;
Be careful to recall this is different from: 
    j=j+1;
    smaller[j]=a[i];
which is the equivalent of smaller[++j]=a[i], and remember that the ++ operators change the value of an integer variable permanently, so don't think that smaller[j++]=a[i] is the same as smaller[j+1]=a[i] where there is nothing to change the value of j.

You can find code for constructive quicksort of arrays of integers in the form given here in the files QuickSort3.java and QuickSort4.java. The second of these does not print the sorted array, but gives timing figures, so you can use it to check the time taken to sort a very large sized array.

There is an inefficiency in this code, because it compares each element against the pivot twice, first to find the size of the two smaller arrays, and then to decide for each element which array it should go into. Here is a way that could be used to get round this: 

 public static Integer[] sort(Integer[] a)
 {
  if(a.length==0)
     return new Integer[0];
  else if(a.length==1)
     {
      Integer[] b = new Integer[1];
      b[0]=a[0];
      return b;
     }
  else
     {
      Integer pivot = a[0];
      boolean[] greaterthan = new boolean[a.length];
      int count=0;
      for(int i=0; i<a.length; i++)
         if(a[i].compareTo(pivot)<0)
            count++;
         else
            greaterthan[i]=true;
      Integer[] smaller = new Integer[count];
      Integer[] greater = new Integer[a.length-count-1];
      for(int i=1, j=0, k=0; i<a.length; i++)
         if(greaterthan[i])
            greater[j++]=a[i];
         else
            smaller[k++]=a[i];
      smaller = sort(smaller);
      greater = sort(greater);
      Integer[] b = new Integer[a.length];
      for(int i=0; i<count; i++)
         b[i]=smaller[i];
      b[count]=pivot;
      for(int i=0; i<greater.length; i++)
         b[count+i+1]=greater[i];
      return b;
     }
 }
Here we create a temporary array of booleans of the size of the array being sorted, and go through the array of elements, in each case where an element is greater than the pivot setting the same position in the array of booleans to true. When a new array of booleans is created, all its positions are initialised to false, so the other position remain set to false. We also do the counting as before. After that, instead of doing the checking against the pivot again, whether an element is put into the smaller or greater is decided by what value is stored in its position in the array of boolean.

You can find code for this form of constructive quicksort of arrays of integers in the files: QuickSort3a.java and QuickSort4a.java. Again, the second of these can be used to get timing figures for sorting very large arrays. If you compare the time taken to sort an array of a particular size and range with the time taken using QuickSort4.java to sort an array of the same size and range, you should find it is significantly less. Comparing integers is done in one step, so this would be even more of an issue if we were sorting an array of elements which involved some longer calculation to determine whether one is less than another.

Quicksort in Place

A simple way of obtaining destructive quicksort would be to copy the elements from the two sorted arrays in the above code back into the original array rather than into a new array, but otherwise use code similar to the constructive quicksort given above. This would give the code: 

 public static void sort(Integer[] a)
 {
  if(a.length>1)
     {
      Integer pivot = a[0];
      int count=0;
      for(int i=0; i<a.length; i++)
         if(a[i].compareTo(pivot)<0)
            count++;
      Integer[] smaller = new Integer[count];
      Integer[] greater = new Integer[a.length-count-1];
      for(int i=1, j=0, k=0; i<a.length; i++)
         if(a[i].compareTo(pivot)<0)
            smaller[j++]=a[i];
         else
            greater[k++]=a[i];
      sort(smaller);
      sort(greater);
      for(int i=0; i<count; i++)
         a[i]=smaller[i];
      a[count]=pivot;
      for(int i=0; i<greater.length; i++)
         a[count+i+1]=greater[i];
     }
 }
and you can find this code in the files QuickSort5.java and QuickSort6.java. Although this is destructive, since the array passed as an argument is changed, it does involve the construction of the two temporary arrays indexed by smaller and greater, and when each of these are sorted further temporary arrays are created as the algorithms is executed recursively. Since it is destructive, new arrays are not created in the base case when the array being sorted is of length 1 or 0. As previously, it could have been made more efficient by using the technique of having an array of booleans to avoid checking each element twice.

However, there is another version of quicksort on arrays which does not involve any construction of new arrays at all. Instead it works just by swapping the elements around in the array, as we saw previously with the destructive selection sort. This is referred to as quicksort in place

The algorithm is the same before: divide the array into two portions, one containing all the elements less than the pivot, the other containing all the elements greater than or equal to the pivot, then sort each of these two portions recursively. However, in this case instead of creating new arrays, we move the elements about in the original array until they are in positions where one section of the array is smaller elements and the other section is larger elements. We do not know at the start how many elements are less than the pivot and how many are greater, so the two sections are not necessarily equal in length. The base case is when the section being sorted has 0 or 1 elements in it.

There are several variations on the way this can be coded, but they all work on the principle of starting with two indexes to the portion of the array being sorted, one indexing either end. The lower one is increased to index further up the array and the higher one is decreased to index lower down the array, until the lower one indexes an element greater than or equal to the pivot and the upper one indexes an element less than the pivot. These two elements are then swapped in position. This is repeated until the two indexes have crossed over. At that point, the array has been partioned into a smaller and larger section, and these sections are sorted recursively.

Here is some code to do this: 

 public static void sort(Integer[] a)
 {
  sort(a,0,a.length);
 }

 private static void sort(Integer[] a,int from,int to)
 {
  if(to>from+1)
     {
      Integer pivot = a[from];
      int low=from+1,high=to-1;
      while(low<high)
         {
          while(low<high&&a[low].compareTo(pivot)<0)
              low++;
          while(pivot.compareTo(a[high])<0)
              high--;
          if(low<high)
            {
             swap(a,high,low);
             low++;
             high--;
            }
         }
      while(pivot.compareTo(a[high])<0)
         high--;
      swap(a,from,high);
      sort(a,from,high);
      sort(a,high+1,to);
     }
 }

 private static void swap(Integer[] a,int pos1,int pos2)
 {
  Integer temp = a[pos1];
  a[pos1]=a[pos2];
  a[pos2]=temp;
 }
In this version, the first element in the section of the array being sorted is used as the pivot. Once the high index has crossed with the low index it may need to be moved down further until it indexes an element less than or equal to the pivot, which thus must be the last element in the smaller valued section of the array. This element is swapped with the pivot element, so the pivot element is positioned between the smaller elements and the larger elements. When the recursive sorts are finished, the whole array will then be sorted.

The work of the sorting is done in the method sort which takes three arguments, a reference to the array, the position of the first element in the section of the array which is currently being sorted, and the position following the position of the last element in the section of the array being sorted. Initially this method is called with the two positions being0 and the length of the whole array. So note that instead of actually creating separate arrays to sort using a recursive method, we have a method which sorts a section of one array, and recursive calls sort smaller sections of the same array.

Let us consider an example. Suppose the whole array being sorted is 

[30,25,47,99,8,12,28,63,16,20]
Then we take 30 as the pivot, and start with the low index at 1 and the high index at 9 (the index of the last component of the array). Then the low index is increased until it has the value 2 which indexes 47 which is greater than 30, and the high index remains at 9 as this indexes the value 20, which is less than 30. Swapping 47 with 20 gives: 
[30,25,20,99,8,12,28,63,16,47]  low=2  high=9
The low index is increased by one and indexes the number 99 which is greater than 30. The high index is decreased by one and indexes the number 16 which is less than 30. These two numbers are swapped round giving: 
[30,25,20,16,8,12,28,63,99,47]  low=3  high=8
Now low is increased until it indexes the next element which is greater than the pivot, which is 63 at position 7 while high is decreased until it indexes the next element which is less than the pivot, which is 28 at position 6. At this point, high and low have crossed over. 
[30,25,20,16,8,12,28,63,99,47]  low=7  high=6
Swapping the pivot with the element indexed by high gives: 
[28,25,20,16,8,12,30,63,99,47]
We can now recursively sort the portion of the array [28,25,20,16,8,12] and the portion [63,99,47]. But there is no need to copy the numbers into separate arrays to do this, we just call the sort method with the whole array, 0 and 6 as its arguments to sort the first part, and with the whole array, 7 and 10 to sort the second part. When both parts are sorted, the whole array is sorted.

Code for this version of quicksort can be found in the files QuickSort7.java and QuickSort8.java. Code using the same algorithm, but applied to an arrayList rather than an array can be found in the files QuickSort9.java and QuickSort10.java.

Merge Sort of arrays

The merge sort algorithm, which we saw previously with Lisp lists can also be applied to arrays. Since merge sort works by dividing the original array into two equally sized halves, we can create these half sized arrays immediately and sort them (note they will differ in size by one if the original array is of odd length). It does not matter which elements go into each half, since in merge sort the work of comparing elements is done after the recursive calls when the sorted collections are merged.

Here is code for merge sort of an array of integers: 

 public static void sort(Integer[] a)
 {
  if(a.length>1)
     {
      int i,mid = a.length/2;
      Integer[] half1 = new Integer[mid];
      Integer[] half2 = new Integer[a.length-mid];
      for(i=0; i<mid; i++)
         half1[i]=a[i];
      for(; i<a.length; i++)
         half2[i-mid]=a[i];
      sort(half1);
      sort(half2);
      int j=0, k=0;
      for(i=0; j<half1.length&&k<half2.length; i++)
         if(half1[j].compareTo(half2[k])<0)
            {
             a[i]=half1[j];
             j++;
            }
         else
            {
             a[i]=half2[k];
             k++;
            }
      for(; j<half1.length; i++, j++)
         a[i]=half1[j];
      for(; k<half2.length; i++, k++)
         a[i]=half2[k];
     }
 }
The code before the recursive calls 
sort(half1);
sort(half2);
creates two new arrays, and then copies the elements from the first half of the original array into one of them, and copies the elements from the second half into the other. The recursive calls apply the same algorithm on these two arrays. The base case is when the array is of length 0 or 1, so as the recursive calls are guaranteed to be on arrays of smaller size than the original array, the base case will eventually be reached.

The code after the recursive calls merges the two sorted temporary arrays, referred to by variables half1 and half2, back into the space of the original array referred to by variable a. It uses the technique we saw with partioning in constructive quicksort of an index for each of the individual arrays, again with the names i for the main array and j and k for the smaller arrays. Again, i is increased each time round the loop, and either j or k as appropriate, but not both, is increased each time round the loop. The merge part looks at the element in the array half1 indexed by j and the element in the array half2 indexed by k. It copies whichever of them is smaller into a[i] and increases the index of whichever array it was copied to by one, so next time round the loop the following element in the array is looked at.

We can consider how this algorithm works on the array we used before, [30,25,47,99,8,12,28,63,16,20]. It is divided into two halves, [30,25,47,99,8] and [12,28,63,16,20]. Sorting these gives [8,25,30,47,99] and [12,16,20,28,63]. Now let us consider merging them. We have: 

[_,_,_,_,_,_,_,_,_,_] i=0   [8,25,30,47,99] j=0   [12,16,20,28,63] k=0
The first array here actually still stores the numbers in their original order, but that is irrelevant as they will be overwritten in the merger. Here, starting off with i, j and k all at 0, half1[j] is 8 and half2[k] is 12, so half1[j] is the lower, it is copied into a[i] and j is increased by one, giving: 
[8,_,_,_,_,_,_,_,_,_] i=1   [8,25,30,47,99] j=1   [12,16,20,28,63] k=0
Now half2[k] is lower than half1[j] so it is copied into a[i] and k is increased by one giving: 
[8,12,_,_,_,_,_,_,_,_] i=2   [8,25,30,47,99] j=1   [12,16,20,28,63] k=1
And now half2[k] is lower than half1[j] again, so it is copied into a[i] and k is increased by one again, giving: 
[8,12,16,_,_,_,_,_,_,_] i=3   [8,25,30,47,99] j=1   [12,16,20,28,63] k=2
Once again, half2[k] is lower than half1[j], so the situation becomes: 
[8,12,16,20,_,_,_,_,_,_] i=4   [8,25,30,47,99] j=1   [12,16,20,28,63] k=3
But now half1[j] is lower than half2[k], so the situation becomes: 
[8,12,16,20,25,_,_,_,_,_] i=5   [8,25,30,47,99] j=2   [12,16,20,28,63] k=3
You can see that by carrying on this work, the original array will be filled with the elements from the other two arrays in sorted order. Actually, it won't quite work like this, it will always be the case that j reaches the length of half1 when k hasn't reached the length of half2, or the other way round. Once the all the elements from one of the arrays have been copied into the original array, any elements left in the other array have to be copied in after them, that is why we have the additional statements: 
  for(; j<half1.length; i++, j++)
     a[i]=half1[j];
  for(; k<half2.length; i++, k++)
     a[i]=half2[k];
The body in one or other of these loops will be executed, depending on whether j is less than half1.length or k is less than half2.length, to copy the remaining elements into the original array. The other loop will only get as far as the loop test which will be false before the body is executed.

Code for merge sort of arrays of integers, together with support code to give your own integers, generate and print random integers, or generate random integers and sort them but just give timing figures can be found in the files MergeSort1.java, MergeSort3.java and MergeSort5.java. There is also code, with similar supporting code, to merge sort arrays of strings in the files MergeSort2.java, MergeSort4.java and MergeSort6.java. You will need the file WordGen.java to generate random strings.

Merge sort can be applied to arrayLists as well as to arrays. The files MergeSort7.java and MergeSort8.java show merge sort applied to arrayLists.

Note the merge sort code we have given here is destructive, because the merger puts the sorted objects back into the same array or arrayList object they came from originally. If they were instead put into a new array or arrayList, we would obtain constructive merge sort.

Recursion Expressed using Iteration with a Stack and a Nested Class

When a method call is made, a new environment for that method call is created, the method call is executed in that environment, and then execution returns to the environment it was in previously, which is the method call that made the method call. So as method calls make method calls, a stack of environments is built up. The current environment is at the top of the stack. When a method is called a new environment is added to the top of the stack. When a method call terminates, its environment is taken off the top of the stack.

To show that there is nothing “magic” about recursion, we can look at how a method that is usually expressed recursively can be implemented purely iteratively if, instead of using recursion, there is an explicit stack of the values that would otherwise be in the method call environments. Here is destructive quicksort of an array expressed in that way: 

 public static void sort(Integer[] a)
 {
  ArrayList<Pair> stack = new ArrayList<Pair>();
  stack.add(new Pair(0,a.length));
  while(stack.size()>0)
     {
      Pair p=stack.remove(stack.size()-1);
      int from=p.from;
      int to=p.to;
      if(to>from+1)
         {
          Integer pivot = a[from];
          int low=from+1,high=to-1;
          while(low<high)
             {
              while(low<high&&a[low].compareTo(pivot)<0)
                  low++;
              while(pivot.compareTo(a[high])<0)
                  high--;
              if(low<high)
                {
                 swap(a,high,low);
                 low++;
                 high--;
                }
             }
          while(pivot.compareTo(a[high])<0)
             high--;
          swap(a,from,high);
          stack.add(new Pair(from,high));
          stack.add(new Pair(high+1,to));
         }
     }
 }
The stack is given by an arrayList of Pair objects, where a Pair just holds two integer values, from and to. Initially the stack is set to hold the pair 0 and a.length where a is the array, just as the initial call to the recursive method in the code above had these as its arguments. In the place of the recursive calls in that code, new pairs are added to the stack. There is a loop which takes the pair off the top of the stack and executes the equivalent of the recursive method call with the from and to values of that pair. When the stack becomes empty it is the equivalent of all recurisve calls having been made, so the original call is returned to, and the computation terminates.

The following here is the code for class Pair: 

 private static class Pair
 {
  int from, to;

  Pair(int f,int t)
  {
   from=f;
   to=t;
  }
 }
This can be declared as a nested class, which is the class equivalent of a helper method, that is a class declared only to be used internally by code in another class. Java allows a class to be declared inside another class. Like a method, a class declared inside another class may be declared as static meaning it is self-contained. If it is not declared as static it is called an inner class. There are additional issues with inner classes, but a static nested class is no different than any other class, except it can only be used directly in code in the class it is in. Because it can only be used in that limited way, the usual rule of practice that variables in a class must be declared as private and accessed only through public methods does not have to be applied. So, the variables from and to in Pair objects used in the sort code are accessed directly, this is not a problem since no code in other classes could access them and change them. If you have code which requires a collection of values grouped together, such as here where from-to pairs are required, the way to do it is to declare a small nested class like this.

You can find the code for this non-recursive implementation of quicksort in the files QuickSort11.java and QuickSort12.java. Note, you do not need a separate file for the class Pair since as it is a nested class its code is inside these files. QuickSort12.java has the front-end which gives the time taken, so you can compare it with the equivalent recursive code in QuickSort8.java. People who find recursion difficult to understand often don't use it and instead write more complicated non-recursive code, making the excuse that they are doing that “because recursion is less efficient”. However, if you run these two programs, you will find the recursive version, if anything, teds to run quicker than the iteratuve version, not slower.

Java's sorting methods

Sorting is such a fundamental task in computing that anyone who deserves the description “Computer Scientist” ought to have a good familiarity with the main sorting algorithms. It also helps us develop an understanding of algorithms and of how code translates algorithms into something the computer can obey to see these sorting algorithms and to see Java code for them. However, in practice as a Java programmer you would not have to write your own code to sort arrays of data. It is such a common operation that the Java library provides code for you which does the job. Not only does this mean you don't have to write your own code, you can also be sure that the developers of the Java language put a lot of thought into the code library they distribute with it. You can therefore be sure that the array sorting methods they provide do not contain any errors and are written to be the most efficient algorithm for sorting (2).

The philosophy of the Java language is to re-use code wherever possible. So it's always a good idea to see if the Java language already supplies code in its code library to fill a need you have, rather than write code yourself. It is not impossible for code supplied from elsewhere to be contain errors. It is however much more likely to be error‑free than code you have written yourself, in particular if you are using it in a standard way to do standard tasks, and it has been provided by a trusted provider. As a novice programmer, you can safely assume that the Java compiler and Java library code will always work correctly - if your code does not work, it will be because of an error or a misassumption you have made, not because of an error in the compiler or library code.

The Java class Arrays contains a range of static methods for doing common array operations. It has a static method called sort which destructively sorts arrays of any objects. So Arrays.sort(a) where a refers to an array will change the array that a refers to so that it is sorted. Note that the sorting it does is in the order given by the compareTo method of the objects it is sorting. For example, if str1 and str2 are of type String then str1.compareTo(str2) gives a negative number if str1 comes before str2 alphabetically, and a positive number if str1 comes after str2 alphabetically. This means that if a is of type String[] then Arrays.sort(a) will sort the array referred to by a into alphabetical order. This is not the only possible ordering you might want to apply to an array of strings. For example, you might want to sort an array of strings in order of their length rather than alphabetically. We will see later how code for sorting can be generalised to allow different orderings to be specified. The ordering given by an object's compareTo methods is referred to as the natural ordering.

Even with an array of integers, while you might think the only possible ordering you would ever need is the natural ordering of ascending numerical order, there could be other possibilities, apart from the obvious descending numerical order. Suppose, for example, you were running a competition “guess the number of marbles in a jar”, and you knew the answer was 1037. Then if you had guesses stored in an array, you would want to order those guesses in the order “closest to 1037”. In this ordering, 1042 comes before 1027, but after 1039. Again, this illustrates the importance of being precise in your specification. What you assume is the only possible interpretaton of some vaguely worded specification such as “sort this array” may not be the only possible one. It is always good to write specifications for code that has to be written in such a way as there cannot possibly be any alternative way of interpreting the specification.

In the files JavaSort1.java and JavaSort3.java, you will find code that uses Java's sort method to sort an array of randomly generated integers, in the first case displaying the integers before and after sorting, in the second displaying only timing figures. In the files JavaSort2.java and JavaSort4.java, you will find code that uses Java's sort method to sort an array of randomly generated strings (using the file WordGen.java to generate them). The strings are sorted in their default order, which is alphabetical.

The Java class Collections is equivalent to the Java class Arrays but dealing with arrayLists rather than arrays. Actually, it deals with a range of Collection types, of which ArrayList is just one example, but it is the only example we have seen so far. So if a is a variable of type ArrayList<Integer> or ArrayList<String>, or an arrayList of any other element type so long as that element type may have the method compareTo called on it, then Collections.sort(a) will re-order the contents of the arrayList referred to by a according to the ordering given by the compareTo method of the element type. It has several other useful methods as well, for example Collections.max(a) will return the maximum element according to natural ordering in the arrayList referred to by a

In the files JavaSort5.java and JavaSort7.java, you will find code that uses Java's sort method to sort an arrayList of randomly generated integers, in the first case displaying the integers before and after sorting, in the second displaying only timing figures. In the files JavaSort6.java and JavaSort8.java, you will find code that uses Java's sort method to sort an arrayList of randomly generated strings.

Footnotes

(1) You probably would not notice if it wasn't pointed out here, but “quicksort” is written as one word while “merge sort” is written as two words. The reason for this is that quicksort is an algorithm invented by the computer scientist Tony Hoare, who gave it this one word name in his article describing it in the July 1961 edition of the Communications of the ACM. There is no definite claim for the invention of merge sort, although opinion is that it was first described by the computer scientist John von Neumann. It is often assumed that the sorting algorithm Shell sort (which we have not covered in this module) is so named because “shell” refers to an aspect of the algorithm. This algorithm, like quicksort, had a definite inventor who described it in another Communications of the ACM article, his name is Donald Shell, and the algorithm is named after him.

(2) You cannot be completely sure, however. In fact, for many years, Java's sorting code (and sorting code in many other places) contained an error. You can see comment on this error here. The problem would only occur when sorting very large arrays, since it comes about when two array indexes are added in order to get the mid-point, but their sum is greater than the maximum value that can be held in an int variable. In general, library code will have been thoroughly tested by its distributors, and then by being used by all the people who have made use of it - that's much more testing than you would be able to do on code you've written yourself. So while not completely ruling out the possibility that if your code isn't working it's due to an error in library code or the compiler, in general you can assume that if your code isn't working as you expect, even if its failure to work completely baffles you, it's likely to be something you have written or understood wrongly, not the library software you're using which is behaving wrongly. This is particularly so if your programming isn't doing anything very unusual (and nothing you are asked to do in this module will involve code so unusual that it will reveal an error in Java that no-one found before).

Matthew Huntbach

Last modified: 8 March 2019