Is there a sorting algorithm with linear time complexity and O(1) auxiliary space complexity?

Question

Is there a sorting algorithm with linear time complexity and O(1) auxiliary space complexity to sort a list of positive integers? I know that radix sort and counting sort have linear time complexity (O(kn) and O(n+k) respectively if we take k as constant), but both of them have O(n+k) auxiliary space complexity. Is it even possible for a sort to have both of these properties? An example of such a sort would be appreciated.

Answer 1

I wanted to include an algorithm here which is an improvement of Mathphile's first answer. In that case the idea was to shave 1 off of each number in the unsorted suffix of the input (while swapping sorted numbers into the prefix). Whenever a number in the unsorted suffix hits 0 it means it is smaller than any other number in the unsorted suffix (because all numbers are being reduced at the same rate).

There is a major improvement possible: with no change to time complexity we can subtract numbers much bigger than 1 - in fact we can subtract a number equal to the smallest remaining unsorted item. This allows this sort to function well regardless of the numeric sizes of the array items, and on floating point values! A javascript implementation:

let subtractSort = arr => {
  
  let sortedLen = 0;
  let lastMin = 0; // Could also be `Math.min(...arr)`
  let total = 0;
  while (sortedLen < arr.length) {
    
    let min = arr[sortedLen];
    for (let i = sortedLen; i < arr.length; i++) {
      
      if (arr[i]) {
        
        arr[i] -= lastMin;
        if (arr[i]) min = Math.min(min, arr[i]);
        
      } else {
        
        arr[i] = arr[sortedLen];
        arr[sortedLen] = total;
        sortedLen++;
        
      }
      
    }
    
    total += lastMin;
    lastMin = min;
    
  }
  return arr;
  
};

let examples = [
  [ 3, 2, 5, 4, 8, 5, 7, 1 ],
  [ 3000, 2000, 5000, 4000, 8000, 5000, 7000, 1000 ],
  [ 0.3, 0.2, 0.5, 0.4, 0.8, 0.5, 0.7, 0.1 ],
  [ 26573726573, 678687, 3490, 465684586 ]
];
for (let example of examples) {
  console.log(`Unsorted: ${example.join(', ')}`);
  console.log(`Sorted:   ${subtractSort(example).join(', ')}`);
  console.log('');
}

Note this sort only works with positive numbers. To work with negative numbers we would need to find the most negative item, subtract this negative value from every item in the array, sort the array, and finally add the most negative value back to every item - overall this doesn't increase time complexity.

Answer 2

Here is a sort algorithm that has linear time complexity and O(1) auxiliary space complexity. I'll call it subtract-sort. Here is the code in C (runnable here).

// Subtract Sort
#include<stdio.h>
int print_arr(int arr[], int n)
{
  int z;
  for(z=0 ; z<n ; z++)
  {
    printf("%d ", arr[z]);
  }
}
void subtract_sort(int arr[], int arr_size)
{
  int j=0;
  int val=1;
  int all_zero=0;
  while(!all_zero)
  {
    int m;
    all_zero=1;
    int i;
    for(i=j ; i<arr_size ; i++)
    {
      arr[i]--;
      if(arr[i]==0)
      {
        arr[i]=arr[j];
        arr[j]=val;
        j++;
      }
      all_zero=0;
    }
    val++;
  }
}
int main()
{
  int arr[12]={2,10,3,7,9,8,54,3,9,38,8};
  int size=11;
  subtract_sort(arr, size);
  printf("\n--------------------------\n");
  print_arr(arr, size);
  return 0;
}
 

The algorithm has a worst-case time complexity of O(kn), where k is the biggest element of the array. This algorithm is efficient for large arrays containing small values (outperforming quicksort), but very inefficient for small arrays containing large values. The time complexity is also exactly equal to sum(arr) which is the sum of all the elements in the array.

To all those who say that this algorithm does not have linear time, find me an array that exceeds my calculated worst-case time complexity of O(kn). If such a counterexample is found, I will happily agree with you.

Maybe this example of a worst-case scenario would help in understanding the time complexity.

Answer 3

If we are sorting only integers, we can use the in-situ variant of counting sort which has O(k) space complexity, which is independent from the variable n. In other words when we treat k as constant, the space complexity is O(1).

Alternatively, we can use in place radix sort with lg k phases of binary partition with O(lg k) space complexity (due to recursion). Or even less phases with the use of counting sort to determine the buckets boundaries for the n-way partition. These solutions sport time complexity of O(lg k * n), which when expressed only in terms of the variable n is O(n) (when k is considered constant).

Another possible approach to obtain O(n) step complexity and O(1) space complexity, when k is considered constant, is to use something which can be called subtraction sort, as described by the OP in their own answer, or elsewhere. It has step complexity O(sum(input)) which is better than O(kn) (and for certain specific inputs it is even better than binary-radix sort's O(lg k * n), e.g. for all inputs of the form [k, 0, 0, ... 0]) and space complexity O(1).

Yet another solution is to use bingo sort which has step complexity O(vn) where v <= k is the number of unique values in the input, and space complexity O(1).

Note that neither of these sorting solutions are stable, which matters if we sort something more than just integers (some arbitrary objects with integer keys).

There is also a cutting edge stable partition algorithm described in this paper with O(1) space complexity. Combining it with radix sort, one may construct a stable linear sort algorithm with constant space - O(lg k * n) step complexity and O(1) space complexity.

---

EDIT:

As per the request from the comment, I've tried to find a source for the "in-situ" variant of counting sort, but haven't found anything of good quality I could link to (it's really strange that there is no easily available description for such a basic algorithm). Therefore, I'm posting the algorithm here:

The regular counting sort (from Wikipedia)

count = array of k+1 zeros
for x in input do
    count[key(x)] += 1

total = 0
for i in 0, 1, ... k do
    count[i], total = total, count[i] + total

output = array of the same length as input
for x in input do
    output[count[key(x)]] = x
    count[key(x)] += 1 

return output

It assumes that the input consists of some objects which can be identified by an integer key in the range 0 to k - 1. It uses O(n + k) extra space.

The trivial in-situ variant for integers

This variant requires the input to be pure integers, not arbitrary objects with integer keys. It simply reconstructs the input array from the count array.

count = array of k zeros
for x in input do
    count[x] += 1

i = 0
for x in 0, 1, ... k - 1 do
    for j in 1, 2, ... count[x] do
        input[i], i = x, i + 1

return input

It uses O(k) extra space.

The complete in-situ variant for arbitrary objects with integer keys

This variant accepts arbitrary objects similarly to the regular variant. It uses swaps to place objects in appropriate places. After computing the count array in the two first loops it leaves it immutable, and uses another array called done to keep track of how many objects with a given key have been already placed in the right position.

count = array of k+1 zeros
for x in input do
    count[key(x)] += 1

total = 0
for i in 0, 1, ... k do
    count[i], total = total, count[i] + total

done = array of k zeros
for i in 0, 1, ... k - 1 do
    current = count[i] + done[i]
    while done[i] < count[i + 1] - count[i] do
        x = input[current]
        destination = count[key(x)] + done[key(x)]
        if destination = current then
            current += 1
        else
            swap(input[current], input[destination])
        done[key(x)] += 1 

return input

This variant is not stable, so it cannot be used as a subroutine in radix sort. It uses O(2k) = O(k) extra space.

Answer 4

Here is another example of a sort algorithm that has linear time complexity (if k is taken as constant), O(1) auxiliary space complexity, and is stable too. This is an implementation I wrote of the "binary radix sort" that user ciamej told about in his answer. I could not find any implementation of this algorithm on the internet which satisfied all 3 properties which is why I felt it would be a good idea to add it over here. You can try it here.

// Binary Radix Sort
#include<stdio.h>
#include<math.h>
int print_arr(int arr[], int n)
{
  int z;
  for(z=0 ; z<n ; z++)
  {
    printf("%d ", arr[z]);
  }
  printf("\n");
}
int getMax(int arr[], int n) 
{ 
  int mx = arr[0]; 
  for (int i = 1; i < n; i++) 
      if (arr[i] > mx) 
          mx = arr[i]; 
  return mx; 
} 
void BinaryRadixSort(int arr[], int arr_size)
{
  int biggest_int_len = log2(getMax(arr, arr_size))+1;
  int i;
  int digit;
  for(i=1 ; i<=biggest_int_len ; i++)
  {
    digit=i;
    int j;
    int bit;
    int pos=0;
    int min=-1;
    int min2=-1;
    int min_val;
    for(j=0 ; j<arr_size ; j++)
    {
      int len=(int) (log2(arr[j])+1);
      if(i>len)
      {
        bit=0;
      }
      else
      {
        bit=(arr[j] & (1 << (digit - 1)));
      }
      if(bit==0)
      {
        min_val=arr[j];
        min=j;
        min2=j;
        break;
      }
    }
    while(min!=-1)
    {
      while(min>pos)
      {
        arr[min]=arr[min-1];
        min--;
      }
      arr[pos]=min_val;
      pos++;
      int k;
      min=-1;
      for(k=min2+1 ; k<arr_size ; k++)
      {
        int len=(int) (log2(arr[k])+1);
        if(i>len)
        {
          bit=0;
        }
        else
        {
          bit= arr[k] & (1 << (digit-1));
        }
        if(bit==0)
        {
          min_val=arr[k];
          min=k;
          min2=k;
          break;
        }
      }
    }
  }
}
int main()
{
  int arr[16]={10,43,73,14,64,2,6,1,5,3,6,3,5,8,4,5};
  int size=16;
  BinaryRadixSort(arr, size);
  printf("\n--------------------------\n");
  print_arr(arr, size);
  return 0;
}

The time complexity of this algorithm is O(log2(k).n), where k is the biggest number in the list and n is the number of elements in the list.