Sorting in Linear Time

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa

Abstract:

Sorting has been researched for many years now, resulting in the development of various algorithms that are highly efficient both in time and the amount of memory used. One of the most common sorts is the QuickSort which has been refined to sort very efficiently in most cases. However, the problem with algorithms such as quicksort is that they are comparison based and all such algorithms have a lower bound time complexity of O(n*log(n)).
This project involves the development of an algorithm that is capable of sorting in linear time. It is similar to the radix sort method in the way it that it breaks up the items that need to be sorted; however, the method used to perform the actual sort is significantly different.

Calendar:

• Project Started:
  8th April 2002



• Presentation at Europa:
  14th May 2002



• Implementation using RESOLVE/C++:
  Completed 12th May 2002



• Implementation using C:
  Completed 10th August 2002

Project Development:

Spring 2002

Theoretically this algorithm should take linear time to sort an array of words (strings of characters);however, the sorting process needs to create a highly complex data structure in order to perform its job. This led to the belief that even though it would sort in linear time, the time and memory overhead involved in creating the required data structures would result in a very large constant, rendering the algorithm useless for practical applications.

This idea of impracticallity lead to the implementation using RESOLVE/C++ which is known to be highly inefficient in development of time critical code. What makes this language useful is the simplicity of the coding involved and the presence of various components that make it perfetf for rapid development.

The first implementation was completed in about a weeks time leading to a revelation that after all the algorithm is not as bad as I had initially assumed it to be. Even though the time constant involved was extremenly large, making the code useless for sorting a few items, it was ofset by the fact that the algorithm was linear, leading to shorter sorting times for a large number of words. When timed against the quicksort implementation present as a component in the RESOLVE Catalog it was found that the new algorithm could sort faster than quicksort when the number of items to be sorted was greater than 20,000.

Even though the this implementation seemed to be comparable to the quicksort in RESOLVE/C++, it was significantly slower than the Unix sort command. Applications developed in RESOLVE/C++ are known to be inefficient because of the extreme complexity aquired by making the code more general and easier to read and mantain. Also since the algoritm required building of a massive tree structure it need to allocate memory very often. This would lead to fragmentation which added on to the ineffciency. Furthermore the recursion was used in the implementation which is not efficient. This led to a new implementation using ANSI C in which recursion was avoided and memory management was made more efficient by allocating large amounts of memory at a time.

The C implementation resulted in a code that was lot faster than the RESOLVE/C++ implementaion of the algorithm. It is also comparable to the unix sort command in the amount of time it takes to sort words using ASCII ordering.

Findings and Contributions:

Comparing the timing results of the RESOLVE/C++ implemenation and the one using C led me to conclude that RESOLVE/C++ was indeed very inefficient compared to C/C++. This led me into my next project which dealt with finding out what slowes down RESOLVE/C++ and if possible to find out means to improve it.

Links and References:

Presentation
Resolve/C++ Implementation of the algorithm
C Implementations of the algorithm

  Return to Europa