Best continuously sorting algorithm?

Question

I have a set of double-precision data and I need their list to be always sorted. What is the best algorithm to sort the data as it is being added?

As best I mean least Big-O in data count, Small-O in data count (worst case scenario), and least Small-O in the space needed, in that order if possible.

The set size is really variable, from a small number (30) to lots of data (+10M).

Answer 1

By a "set of double data," do you mean a set of real-valued numbers? One of the more commonly used algorithms for that is a heap sort, I'd check that out. Most of its operations are O( n * log(n) ), which is pretty good but doesn't meet all of your criteria. The advantages of heapsort is that it's reasonably simple to code on your own, and many languages provide libraries to manage a sorted heap.

Answer 2

Likely a heap sort. Heaps are only O(log N) to add new data, and you can pop off the net results at any time in O(N log N) time.

If you always need the whole list sorted every time, then there's not many other options than an insertion sort. It will likely be O(N^2) though with HUGE hassle of linked skip lists you can make it O(N log N).

Answer 3

Building a self-balancing binary tree like a red-black tree or AVL tree will allow for Θ(lg n) insertion and removal, and Θ(n) retrieval of all elements in sorted order (by doing a depth-first traversal), with Θ(n) memory usage. The implementation is somewhat complex, but they're efficient, and most languages will have library implementations, so they're a good first choice in most cases.

Additionally, retreiving the i-th element can be done by annotating each edge (or, equivalently, node) in the tree with the total number of nodes below it. Then one can find the i-th element in Θ(lg n) time and Θ(1) space with something like:

node *find_index(node *root, int i) {
  while (node) {
    if (i == root->left_count)
      return root;
    else if (i < root->left_count)
      root = root->left;
    else {
      i -= root->left_count + 1;
      root = root->right;
    }
  }
  return NULL; // i > number of nodes
}

An implementation that supports this can be found in debian's libavl; unfortunately, the maintainer's site seems down, but it can be retrieved from debian's servers.

Answer 4

Check out the comparison of sorting algorithms in Wikipedia.

Answer 5

The structure that is used for indexes of database programs is a B+ Tree. It is a balanced bucketed n-ary tree.

From Wikipedia:

For a b-order B+ tree with h levels of index:

• The maximum number of records stored is n = b^h
• The minimum number of keys is 2(b/2)^(h−1)
• The space required to store the tree is O(n)
• Inserting a record requires O(log-b(n)) operations in the worst case
• Finding a record requires O(log-b(n)) operations in the worst case
• Removing a (previously located) record requires O(log-b(n)) operations in the worst case
• Performing a range query with k elements occurring within the range requires O(log-b(n+k)) operations in the worst case.

I use this in my program. You can add your data to the structure as it comes and you can always traverse it in order, front to back or back to front, or search quickly for any value. If you don't find the value, you will have the insertion point where you can add the value.

You can optimize the structure for your program by playing around with b, the size of the buckets.

An interesting presentation about B+ trees: Tree-Structured Indexes

You can get the entire code in C++.

---

Edit: Now I see your comment that your requirement to know the "i-th sorted element in the set" is an important one. All of a sudden, that makes many data structures less than optimal.

You are probably best off with a SortedList or even better, a SortedDictionary. See the article: Squeezing more performance from SortedList. Both structures have a GetKey function that will return the i-th element.

Answer 6

I would use a heap/priority queue. Worst case is same as average case for runtime. Next element can be found in O(log n) time.

Here is a templatized C# implementation that I derived from this code.

Answer 7

Ok, you want you data sorted, but you need to extract it via an index number.

Start with a basic Tree such as the afforementioned Red-Black trees.

Modify the tree algo such that as you insert elements into the tree all nodes encountered during insertion and deletion keep a count of the number of elements under each branch.

Then when you are extracting data from the tree you can calculate the index as you go, and know which branch to take based on whether is greater or less than the index you are trying to extract.

One other consideration. 10M elements+ in a tree that uses dynamic memory allocation will suck up alot of memory overhead. i.e. The pointers may take up more space than your actual data, plus whatever other member is used to implement the data structure. This will lead to serious memory fragmentation, and in the worst cases, degrade the system's overall performance. (Churning data back and forth from virtual memory.) You might want to consider implementing a combination of block and dynamic memory allocation. Something where in you sort the tree into blocks of data, thus reducing the memory overhead.

Answer 8

Randomized Jumplists are interesting as well. They require less space as BST and skiplists. Insertion and deletion is O(log n)

Answer 9

If you just need to know the ith smallest element as it says in the comments, use the BFPRT algorithm which is named after the last names of the authors: Blum, Floyd, Pratt, Rivest, and Tarjan and is generally agreed to be the biggest concentration of big computer science brains in the same paper. O(n) worst-case.