6 ms·

A really cool algorithmic problem I've been obsessed with lately is stable sorting in O(n log n) time and O(1) extra space. It's possible (Trabb Pardo 1977, Kat

A really cool algorithmic problem I've been obsessed with lately is stable sorting in O(n log n) time and O(1) extra space. It's possible (Trabb Pardo 1977, Katajainen and Pasanen, Huang and Langston, etc.) but all known algorithms are very complicated. As far as I understand now, there seems to be a "wall" at sqrt(n) extra space. If we have that much, it's not too hard to write a stable mergesort or quicksort with the right time complexity. But if we are restricted to O(1) or O(log n) space, the algorithms become much more involved, using a sqrt(n) buffer inside the array to encode information about the rest. There are working implementations on GitHub (GrailSort and WikiSort), both are over 500 lines. Here's a couple innocent-looking special cases that are still surprisingly hard: 1) Given an array [a1, a2, ..., an, b1, b2, ..., bn], rearrange it into [a1, b1, a2, b2, ..., an, bn] using O(n) time and O(1) extra space. 2) Given an array of zeroes and ones, sort it stably using O(n) time and O(1) extra space. I'd be very interested to hear about any advances in this area.

amelius 10y ago
Interesting problems. But is there a practical reason why you'd want to put such stringent restriction on extra space? I mean, space is relatively cheap nowadays (except of course if locality of reference/cache size is an issue, where it translates back into time).
- gpderetta 10y ago
  a) allocating the extra space might be expensive. and most importantly: b) you might not have extra space. For example, if you are implementing an out of core sort (i.e. sorting huge on-disk datasets), you want to maximize the size of the chunk you will sort in memory and do not want to waste any memory for the temporary storage. (this is related to locality of reference of course, you can a make similar argument for out-of-cache sorting).
  - cousin_it 10y ago
    On one hand, amelius is right, there are already simple fast stable sorts using O(sqrt(n)) extra space and that should be okay for all practical purposes. (Though they aren't very well known, and inventing one will take you a week or two.) Allocating 30K elements to help sort a billion elements is no big deal, you don't need to squeeze further. My interest is more academic, how come the known O(1) solutions are so complex compared to O(sqrt(n)) and can they be simplified.
    - mehaveaccount 10y ago
      I didn't know about this problem before but now I'm incredibly curious. I love these problems where you find a trade-off between two seemingly unrelated things, here how going from o(sqrt(n)) to o(log(n)) memoey increases the code complexity by order of magnitude. If you take the code for an o(1) or o(log(n)) memory sorting algorithm, I wonder if you can identify a subroutine that if memoized would give you an o(sqrt(n)) memory sorting algorithm you already know.
      - cousin_it 10y ago
        I mentioned that in the first comment. Fast in-place stable sorts usually have a step where they must freely rearrange some things (blocks, medians, etc.) and remember their original order, to preserve stability in case some of them were equal. It seems like no one can squeeze the number of these things below sqrt(n). If you have sqrt(n) extra space, you can store a permutation there. If you don't, you use part of the array itself as temporary bit storage, by changing the relative positions of elements. That's where the complexity comes from.
coderfreak333 10y ago
The both problems that you mentioned are quite similar, IMO
- cousin_it 10y ago
  The first has a simple solution if you know some university-level math. The second has no simple solution AFAIK.
  - openasocket 10y ago
    I must be missing something, because problem 2 seems easy. It's just an array of boolean values, right? So you just pass over the array once, counting the number of zeroes. Then pass of the first n elements (for n the number of zeroes) and write zero to them, and write one to all the rest of the array. That's clearly stable (right?), requires only two passes over the array so it's O(N) time, and the only memory used is an index for looping and the count of the number of zeroes so it's O(1) memory. I'm guessing I'm missing something important, what is it?
    - mkingston 10y ago
      Suppose you have a type A ('0' in the original description) and a type B ('1' in the original description). Suppose any instance of A < any instance of B, but any given instance of A is not necessarily even comparable to another instance of A. Similarly any instance of B is not necessarily comparable to another instance of B. Now stably sort an array containing instances of A and B.
      - openasocket 10y ago
        OK, now I see why this is hard, thanks. Now I'm gonna spend the next few days mulling over this problem :) I noticed the problem is relatively easy if you're dealing with a linked list instead of an array, because you can easily move elements around. If there's some way to amortize that in the array case...
throwaput 10y ago
On the first glance the first problem seems quite impossible. For example, if n is power of two, then for each prime number < n there will be a cycle starting with that number. If n is not a power of two, I haven't yet seen any good explanation of cycles. Any hints? We can't use a or b in any way?
- throwaput 10y ago
  Even for power of two it's not correct, forget my statement about cycles.
  - throwaput 10y ago
    Yet I have only one idea - that we can permute the elements somehow (in a O(1) reversible way like a Gray code) so that the cycles would form something computable in O(n) time and O(1) space
- davidtgoldblatt 10y ago
  I think you're on the right track (i.e. viewing it as a permutation, and looking at the cycle decomposition of that permutation). Try indexing from 0 instead of 1 if you're not. Then the cycle containing 1 will start with (1, 2, 4, 8, ...). What happens when it wraps around?
pklausler 10y ago
> 2) Given an array of zeroes and ones, sort it stably using O(n) time and O(1) extra space. I'm missing something here. If the array's values truly are all in {0,1}, then all the zeroes are indistinguishable and you get stability for free (same for the ones). mysort all01list = let ones = sum all01list in replicate (length all01list - ones) 0 ++ replicate ones 1
- cousin_it 10y ago
  See openasocket's question and mkingston's answer in another subthread.
pierrebai 10y ago
Nit-pick: I believe there are no sorting algorithm in O(1) space: just keeping the index of an element takes log2(N) space. Most algorithms hide this fact by assuming numbers have an infinite range. If you do, then you can use a single data for any algorithm, given a sufficiently clever encoding :) (Just use a number base-N and then you got as much easy-to-access, direct-addressable storage as you want per elements.)
- cousin_it 10y ago
  When people talk about these things, they usually assume something like the transdichotomous model (machine word size is unknown, n fits in a machine word, arithmetic on machine words is O(1)). It gives the right complexities for everyday algorithms.

amelius 10y ago

Interesting problems. But is there a practical reason why you'd want to put such stringent restriction on extra space? I mean, space is relatively cheap nowadays (except of course if locality of reference/cache size is an issue, where it translates back into time).

gpderetta 10y ago
a) allocating the extra space might be expensive. and most importantly: b) you might not have extra space. For example, if you are implementing an out of core sort (i.e. sorting huge on-disk datasets), you want to maximize the size of the chunk you will sort in memory and do not want to waste any memory for the temporary storage. (this is related to locality of reference of course, you can a make similar argument for out-of-cache sorting).
- cousin_it 10y ago
  On one hand, amelius is right, there are already simple fast stable sorts using O(sqrt(n)) extra space and that should be okay for all practical purposes. (Though they aren't very well known, and inventing one will take you a week or two.) Allocating 30K elements to help sort a billion elements is no big deal, you don't need to squeeze further. My interest is more academic, how come the known O(1) solutions are so complex compared to O(sqrt(n)) and can they be simplified.
  - mehaveaccount 10y ago
    I didn't know about this problem before but now I'm incredibly curious. I love these problems where you find a trade-off between two seemingly unrelated things, here how going from o(sqrt(n)) to o(log(n)) memoey increases the code complexity by order of magnitude. If you take the code for an o(1) or o(log(n)) memory sorting algorithm, I wonder if you can identify a subroutine that if memoized would give you an o(sqrt(n)) memory sorting algorithm you already know.
    - cousin_it 10y ago
      I mentioned that in the first comment. Fast in-place stable sorts usually have a step where they must freely rearrange some things (blocks, medians, etc.) and remember their original order, to preserve stability in case some of them were equal. It seems like no one can squeeze the number of these things below sqrt(n). If you have sqrt(n) extra space, you can store a permutation there. If you don't, you use part of the array itself as temporary bit storage, by changing the relative positions of elements. That's where the complexity comes from.

coderfreak333 10y ago

The both problems that you mentioned are quite similar, IMO

cousin_it 10y ago
The first has a simple solution if you know some university-level math. The second has no simple solution AFAIK.
- openasocket 10y ago
  I must be missing something, because problem 2 seems easy. It's just an array of boolean values, right? So you just pass over the array once, counting the number of zeroes. Then pass of the first n elements (for n the number of zeroes) and write zero to them, and write one to all the rest of the array. That's clearly stable (right?), requires only two passes over the array so it's O(N) time, and the only memory used is an index for looping and the count of the number of zeroes so it's O(1) memory. I'm guessing I'm missing something important, what is it?
  - mkingston 10y ago
    Suppose you have a type A ('0' in the original description) and a type B ('1' in the original description). Suppose any instance of A < any instance of B, but any given instance of A is not necessarily even comparable to another instance of A. Similarly any instance of B is not necessarily comparable to another instance of B. Now stably sort an array containing instances of A and B.
    - openasocket 10y ago
      OK, now I see why this is hard, thanks. Now I'm gonna spend the next few days mulling over this problem :) I noticed the problem is relatively easy if you're dealing with a linked list instead of an array, because you can easily move elements around. If there's some way to amortize that in the array case...

throwaput 10y ago

On the first glance the first problem seems quite impossible. For example, if n is power of two, then for each prime number < n there will be a cycle starting with that number. If n is not a power of two, I haven't yet seen any good explanation of cycles. Any hints? We can't use a or b in any way?

throwaput 10y ago
Even for power of two it's not correct, forget my statement about cycles.
- throwaput 10y ago
  Yet I have only one idea - that we can permute the elements somehow (in a O(1) reversible way like a Gray code) so that the cycles would form something computable in O(n) time and O(1) space
davidtgoldblatt 10y ago
I think you're on the right track (i.e. viewing it as a permutation, and looking at the cycle decomposition of that permutation). Try indexing from 0 instead of 1 if you're not. Then the cycle containing 1 will start with (1, 2, 4, 8, ...). What happens when it wraps around?

pklausler 10y ago

> 2) Given an array of zeroes and ones, sort it stably using O(n) time and O(1) extra space. I'm missing something here. If the array's values truly are all in {0,1}, then all the zeroes are indistinguishable and you get stability for free (same for the ones). mysort all01list = let ones = sum all01list in replicate (length all01list - ones) 0 ++ replicate ones 1

cousin_it 10y ago
See openasocket's question and mkingston's answer in another subthread.

pierrebai 10y ago

Nit-pick: I believe there are no sorting algorithm in O(1) space: just keeping the index of an element takes log2(N) space. Most algorithms hide this fact by assuming numbers have an infinite range. If you do, then you can use a single data for any algorithm, given a sufficiently clever encoding :) (Just use a number base-N and then you got as much easy-to-access, direct-addressable storage as you want per elements.)

cousin_it 10y ago
When people talk about these things, they usually assume something like the transdichotomous model (machine word size is unknown, n fits in a machine word, arithmetic on machine words is O(1)). It gives the right complexities for everyday algorithms.