Sorting algorithm that moves element to a 2-dimensional array

Question

I had an idea for a sorting algorithm wich is very fast, but can (potentially) use a lot of memory. I'm not a Computer Science student/graduate, only a self-taught programmer so I don't know how to evaluate it's viability. Also, I would like to know if it has already been documented and under what name.

Algorithm:

• Get an unsorted array
• Iterate through it, and find the highest and lowest value stored in it
• Determine "range" (highest - lowest)
• Make a 2 dimensional array presorted,
  in which the first dimension's size is "range" + 1
• For each element in array "unsorted"
  • Add the current element into presorted[current_element_value - lowest]
• Make array "sorted", and add each element of presorted's second dimension, ignoring the empty first dimensions.
• return the sorted array

An example using said algorithm would be the following:

unsorted[] = {5, 8, 2, 4, 6, 8, 2, 0, 4, 5, 6, 3, 3, 2, 1}

After iterating through it once, we get:
lowest: 0
highest: 8

range = highest - lowest = 8

Make 2 dimensional array presorted,
 consisting of range+1 arrays:

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

Next we add the elements, first element of unsorted is 5.
 5 - lowest (0) is 5

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {5}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

After doing this which each element:

presorted[0] = {0}
presorted[1] = {1}
presorted[2] = {2, 2, 2}
presorted[3] = {3, 3}
presorted[4] = {4, 4}
presorted[5] = {5, 5}
presorted[6] = {6, 6}
presorted[7] = {}
presorted[8] = {8, 8}

Now, we simply create an empty array called "sorted",
 to which we add all the elements
 of non-empty arrays in presorted:

sorted = {0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 8, 8}

This is the C++ source code for it

std::vector<int> Sort(std::vector<int> &unsorted)
{
   int min = unsorted[0];
   int max = unsorted[0];

   int range;

   std::vector<int> sorted;

   for (int i = 0; i < unsorted.size(); i++)
   {
      if (unsorted[i] > max)
         max = unsorted[i];
      if (unsorted[i] < min)
         min = unsorted[i];
   }

   range = max - min;
   std::vector<std::vector<int>> presorted(range+1);

   for (int i = 0; i < unsorted.size(); i++)
       presorted[unsorted[i] - min].push_back(unsorted[i]);

   for (int i = 0; i < presorted.size(); i++)
   {
       if (!presorted[i].empty())
       {
           for (int k = 0; k < presorted[i].size(); k++)
               sorted.push_back(presorted[i][k]);
       }
   }

    return sorted;
}

Is this algorithm viable?

I think it could be used in certain scenarios (when range is not too big) and it has the advantage that you can determine if it's appropriate to use it with simply iterating once through the unsorted list.

I'll do some tests and report back.

Answer 1

What you have come up with is a sligthly less memory efficient version of counting sort.

This algorithm works in $\mathcal{O}(n + range)$ time where $n$ is the number of elements in the vector $unsorted$ and $max$ and $min$ are as defined in your program.

Your implementation uses $\mathcal{O}(n + range)$ memory. You can make it more memory efficient by just keeping track of how many times the same number in the vector 'unsorted' occurs rather than maintaining a vector with repeated instances of the same element i.e.

vector<int> presorted(range+1);
for(int i = 0; i < unsorted.size(); i++)
     presorted[unsorted[i] - min]++

It will now use only $\mathcal{O}(range)$ memory.

Yes you are correct, this method might potentially use up a lot of memory if the difference between the smallest and largest elements of the vector is too great.

For those who are not fluent in C++:

1. OP is finding the smallest and largest elements of the unsorted array $max$ and $min$ respectively.
2. He is initializing an array of size $max - min$ and creating an empty linked list in each position of the array (in this code it is the vector of vector of integers $presorted$).
3. Then each element of $unsorted$ is added as a new node in the linked list at $presorted[unsorted[i] - min]$. In a random access computational model this operation will take $\mathcal{O}(1)$ time and hence each element of $unsorted$ is added to its appropriate bucket in constant time.
4. Then he is just iterating in the array of linked lists and compressing it to the final array $sorted$ which is the final output.