Sorted insertion into small (255 element) list

Question

I am looking for a suitable algorithm to build a relatively small (up to 255 elements) sorted array of integers. The target platform is a STM32 based embedded system. Since memory is limited, an in-place method is preferred.

I am aware that the obvious way is implement and profile the usual suspects (quick sort, insert sert, shell sort), but would like to ask for your experiences nevertheless. More specifically I have found very little information on the performance when building the array - that is, how well different algorithms may use the fact that all existing elements are already ordered.

Edit 1: Although the question is tagged C++ the STL is not available. Furthermore, the sorting does indeed occur inside a inner loop. To further clarify, I am looking for an algorithm that is especially suited to build a sorted list in an efficient manner. I assume (maybe wrongly) there must be algorithms specially suited for this task. That's the question.

Edit 2: When saying building a sorted list I mean that the list starts empty and is filled by by a bounded number (max 255) of 16-bit integers which are in no particular order. The list must be processed after all elements have been stored. For processing the list must be sorted, preferably in descending order.

Thanks in advance, Arne

Answer 1

If your problem demands that:

• you store your elements fully sorted in an actual C/C++ array, and
• you maintain your items in sorted order at all times,

then you've painted yourself into a corner: your requirements spell "insertion sort".

No matter what algorithm or auxiliary datastructure you choose, inserting a new element in the middle will require you to move the larger elements up by an index, and deleting any element (except the largest) will require you to move the larger elements down by an index. Since an insertion sort does exactly that, without any additional logic or datastructure, you might as well use it.

The only exception is if your comparison is particularly expensive. If that is the case, then you can use a binary search to find your insertion point (instead of comparing your new element against each old element as you move it). However, you will still need to move all elements larger than the mutation point, so you will never be able to improve your performance past O(N) (although a bulk data move should be pretty fast...).

Also, you should evaluate your requirements: if you know that N < 256, and the worst case of inserting an object in position 0 is fast enough for your application, you should stop there. There's no point in making things more complicated than necessary, to save time you don't need.

---

On the other hand, if:

• you don't actually need to keep all elements fully sorted at all times, and
• what you do actually need is to repeatedly find and remove the largest/smallest element in the array

then what you need is called a priority queue, and you can implement it (in memory-efficient, in-place fashion) by using an implicit heap. Implicit heap operations are O(log N), and typically have a good performance factor; even for N = 255, this can make a big difference in worst-case performance.

Answer 2

I often use this algo in microcontroller environment, it keeps the table always sorted. It doesn't use binary lookup, but the loop that searches a greater element will run faster then binary algorithm if you only going to use it for a small number of elements. For larger arrays, you may want to do a binary lookup.

This algorithm is also very easy to implement in assembler and only uses 2 additional int's on stack.

#define TABLE_SIZE 255
int table[TABLE_SIZE];
int tableUsed = 0;

bool AddToTable(int value)
{
    int i;

    if (tableUsed >= TABLE_SIZE)
        return false;

    // Find location to insert value
    for (i = 0; i < tableUsed; i++)
        if (table[i] > value)
            break;
    // Insert value
    do
    {
        table[i] ^= value;
        value ^= table[i];
        table[i] ^= value;
    } while (i++ < tableUsed);

    tableUsed++;

    return true;
}