Function bpmnode_sort

dependency/densecrf/examples/lodepng.cpp:731–755

sort the leaves with stable mergesort*/

/*sort the leaves with stable mergesort*/
static void bpmnode_sort(BPMNode* leaves, size_t num)
{
    BPMNode* mem = (BPMNode*)lodepng_malloc(sizeof(*leaves) * num);
    size_t width, counter = 0;
    for(width = 1; width < num; width *= 2)
    {
        BPMNode* a = (counter & 1) ? mem : leaves;
        BPMNode* b = (counter & 1) ? leaves : mem;
        size_t p;
        for(p = 0; p < num; p += 2 * width)
        {
            size_t q = (p + width > num) ? num : (p + width);
            size_t r = (p + 2 * width > num) ? num : (p + 2 * width);
            size_t i = p, j = q, k;
            for(k = p; k < r; k++)
            {
                if(i < q && (j >= r || a[i].weight <= a[j].weight)) b[k] = a[i++];
                else b[k] = a[j++];
            }
        }
        counter++;
    }
    if(counter & 1) memcpy(leaves, mem, sizeof(*leaves) * num);
    lodepng_free(mem);
}

/*Boundary Package Merge step, numpresent is the amount of leaves, and c is the current chain.*/
static void boundaryPM(BPMLists* lists, BPMNode* leaves, size_t numpresent, int c, int num)