Does there exist a stable sorting algorithm that can sort a binary array in O(n) time complexity and O(1) auxiliary space complexity?

Question

I know how to write an algorithm that sorts a binary array in O(n) time and O(1) auxiliary space complexity, but it doesn't seem to be stable.

void binarySort(int arr[], int arr_size)
{
  int i;
  int count_zeros=0;
  for (i=0 ; i<arr_size ; i++)
  {
    if(arr[i]==0)
      count_zeros++;
  }
    int j;
    for(j=0 ; j<count_zeros ; j++)
      arr[j]=0;
    int k;
    for(k=j ; k<arr_size ; k++)
      arr[k]=1;
}

Consider I want to perform binary radix sort using the stable sort algorithm as a subroutine. Here is an example in which we sort we sort according to the least significant bit.

Input: 11, 101, 1000, 1010, 111, 110, 10

Output: 1000, 1010, 110, 10, 11, 101, 111

Notice in the example above, the order of the binary numbers with the same LSBs is preserved.

Is there any way to edit the above algorithm or make a new algorithm such that the sort algorithm is stable while preserving it's O(n) time complexity and O(1) auxiliary space complexity?

From Wikipedia: Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list. For those who say that stability doesn't matter, read this post.

Seems like an intrinsic that counts bits set per word would really help out. https://learn.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=vs-2019 — Michael Dorgan, Aug 28 '20 at 22:31
Or perhaps https://stackoverflow.com/questions/17354971/fast-counting-the-number-of-set-bits-in-m128i-register — Michael Dorgan, Aug 28 '20 at 22:31
Since data is received as array of ints containing 0s and 1s, your method of counting and outputting is fine. Still not sure how stability of sort matters here as there are only 2 states, but it could be that I am just dense... — Michael Dorgan, Aug 28 '20 at 22:57
With pure value types like this, how could it possibly be _unstable_? I don't think the word even applies to this... — Mooing Duck, Aug 28 '20 at 22:58
@MichaelDorgan but I am pretty sure my method of sorting isn't stable. — Mathphile, Aug 28 '20 at 22:58
@MooingDuck What if the binary array corresponds to some list of ordered items? In that case stability matters. — Mathphile, Aug 28 '20 at 23:00
@Mathphile - Then you are sorting indexes and the given sort has no such state. — Michael Dorgan, Aug 28 '20 at 23:01
It sounds like what you're looking for is a stable quicksort partition in O(1) space. [Have a paper on the topic.](http://hjemmesider.diku.dk/~jyrki/Paper/KP1992bJ.pdf) — user2357112, Aug 28 '20 at 23:04
I think that https://stackoverflow.com/questions/2572195/how-is-counting-sort-a-stable-sort might apply as well because you are basically doing a counting sort of 0s and 1s. That link basically states that counting sort is stable so... — Michael Dorgan, Aug 28 '20 at 23:05
Stability is about preserving order of the elements. You're not even preserving the elements, instead writing fresh zeros and ones. I think you'd better pick a more meaningful example, for example sorting Integer objects with values zero or one, or sort arbitrary ints by their modulo-2 value. — superb rain, Aug 28 '20 at 23:17
You're confusing people, because the concept of a stable sort doesn't apply to a binary array. Maybe you want to try something like "Given an array of integers, move even numbers before odd numbers, but otherwise keep the same order" — Matt Timmermans, Aug 28 '20 at 23:23
@Mathphile, there is such an algorithm for a linked list (not an array), since in linked list you can swap sublists in O(1). For arrays, I don't think you can do what you want with O(1) space complexity. — ardenit, Aug 28 '20 at 23:35
@ardenit that is unfortunate if true :( Is there any way to prove this? — Mathphile, Aug 28 '20 at 23:37
@Mathphile Yes, the radix sort application is great. I think [ciamej claimed](https://stackoverflow.com/a/63562729/13008439) that it's possible but failed to demonstrate it and that bothered me. — superb rain, Aug 28 '20 at 23:39
I wonder if you could do it with two index variables. One for the current 0 bit and one for the current 1 bit. Maybe you could make one pass through your input array looking at the least significant bit and swap the entry that has a 0 lsb with the next one that has a 1 lsb and it earlier in the array. I.e. Try to keep your inputs together and swap each 1 and 0 only once working left to right through the array. — Bobby Durrett, Aug 28 '20 at 23:42
@superbrain yes that exact claim by ciamej was what inspired me to ask this question — Mathphile, Aug 28 '20 at 23:54
I guess no. What you are looking for is known as stable partitioning. Check the `Complexity` section of [stable_partition](https://en.cppreference.com/w/cpp/algorithm/stable_partition) page. If the STL didn't come up with the better solution it is likely not exist — user58697, Aug 29 '20 at 00:35
@user58697 What about the paper mentioned earlier? Seems more likely to me that the SL doesn't use it because it's too complicated or too slow in practice. Also if I'm not mistaken, that's just the standard specifying an upper bound, and implementations might provide better complexity. — superb rain, Aug 29 '20 at 00:54
I feel kind of dumb for not being really able to understand the paper. Were you able to understand the algorithm in the paper @superbrain? — Mathphile, Aug 29 '20 at 03:32
@Mathphile I didn't read all the details, but I get the idea. Treat the array of n elements as m = n/(lg n) blocks of size (lg n) each, then sort each block, then rearrange elements so that each block is either only zeros or only ones, then sort the blocks. In ways so that all of those phases take only linear time and constant space. For example the block sorting algorithm takes only O(m) moves of *blocks*. Since there are m=n/(lg n)) blocks of (lg n) elements, that's O(n/(lg n) * (lg n)) = O(n) moves of *elements*. — superb rain, Aug 29 '20 at 10:15
@superbrain thanks that improved my understanding a bit. Could you have a look at my algorithm which I posted below? — Mathphile, Aug 29 '20 at 10:29
@superbrain I stand corrected: the binary-radix sort I was thinking about is either unstable or uses additional space. I will correct my answer shortly :( Then there's the paper from user2357112_supports_Monica, which seems to be stable and constant space. So after all you could implement radix sort with it... — ciamej, Aug 29 '20 at 13:25

Mathphile · Answer 1 · 2020-08-30T23:34:30.873

I think I may have come up with a stable sort algorithm that has O(n) time complexity and O(1) auxiliary space complexity. I would appreciate it if someone could verify that it satisfies all the properties. I would also like to see any other possible approaches to this problem. You can try running it here.

void binarySort(int arr[], int arr_length)
{
  int i, count=1;
  for(i=0 ; i<arr_length ; i++)
  {
    if(arr[i]==1)
    {
      arr[i]=count;
      count++;
    }
  }
  int num0s=arr_length-count+1;
  int j=0;
  int k=0;
  while(j<num0s)
  {
    if(arr[k]==0)
    {
      int temp=arr[k];
      arr[k]=arr[j];
      arr[j]=temp;
      j++;
    }
    k++;
  }
  int a;
  for(a=0 ; a<arr_length-num0s ; )
  {
    if(arr[num0s+a]!=a+1)
    {
      int temp=arr[num0s+a];
      arr[num0s+a]=arr[num0s+temp-1];
      arr[num0s+temp-1]=temp;
    }
    else
    {
      arr[num0s+a]=1;
      a++;
    }
  }
}

For those who are downvoting, I would request them to please explain what is wrong with this algorithm. From what I see, it fulfills all the requirements set.

Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackoverflow.com/rooms/220718/discussion-on-answer-by-mathphile-does-there-exist-a-stable-sorting-algorithm-th). — Samuel Liew, Aug 31 '20 at 05:20

Does there exist a stable sorting algorithm that can sort a binary array in O(n) time complexity and O(1) auxiliary space complexity?

1 Answers1