Thread: merge sort - top down versus bottom up

Originally Posted by rcgldr

My issue is not the overhead of 2 or in this case 3 pointers per recursion call, it's having to repeately traverse at least 1/2 an entire sub-list to find the mid-point.

I understand.

My point was that for some datasets, known to have long already sorted sequences, it just is worth it, compared to plain top-down or bottom-up, or the code complexity of detecting sorted sequences efficiently in a bottom-up merge sort.

Consider a list that is basically a concatenation of three sorted lists. Let's also assume that the second list is at least as long as the third list, for simplicity.

The first list is detected as sorted in the first pass. The first recursive call detects the rest of the second list, and recurses into the third list. The second recursive calls (two calls at the same depth) detect the entire list as sorted. After the merges, all the data is sorted.

This approach works extremely well when the input is mostly sorted. When the input has random sequences, the performance "degrades" gracefully to the top-down merge-sort level, while the code itself is very simple.

Overall, given a mix of almost-sorted data, with a few random sequences (and rarely a purely random list), I just believe this approach is valid. Sure, there are known faster methods, but the simplicity of the code makes this very attractive.

Remember: complex code can have complex bugs, too. In many real world cases, maintainability is more important than a few percent of run time difference.

Originally Posted by rcgldr

Why not just start with the merge operations (bottom up)?

Simply put, I am not convinced yet that there are good bottom-up variants for almost-sorted data.

In particular, consider datasets that are (for whatever reason) usually a few sorted lists concatenated, maybe with a few random nodes sprinkled in, and very rarely completely random lists. (So, no hard limits, just usually almost sorted, very rarely random.)

One approach is a mix, using an initial exploratory pass of the data to see if and where the input contains continuous sorted runs. If there are too many of them (as one can consider a single node as a continuous run of length 1), you fall back to a bottom-up merge sort. (Is there an efficient method to detect unsorted runs? So one could use bottom-up merge sort for unsorted runs, and merge them with sorted runs? Linked list traverses are expensive, so I don't think so.)

What I'd like to see best, is a theoretically sound method of merging a continuous run of sorted nodes (encountered during the bottom-up scan) into the bottom-up doubling-length list array.

(I'm pretty sure there is one. You always know the length of the continuous run; perhaps splitting it into power of two lengths? Or even detecting continuous sorted nodes of power-of-two lengths, and merging them directly to the corresponding arrays? What about order stability?)

Please do note that I'm not claiming you are incorrect; I am just saying I am not convinced yet -- and I suspect that some other members reading this thread share my sentiment. You may very well be right, but I just need to see proof -- for me that means an example.

I must also say that I much prefer seeing the salient code point inline in this post; downloading, extracting, and opening a ZIP file from who knows where (okay, your personal site ) is quite tedious, considering that we're just discussing interesting stuff, not doing in-depth research or actual work. At least I'm here for fun..

Having a full ZIP file test case would be very nice as an addition, if the salient part, the important function, was inline in the message here. Just my opinion, though.

Originally Posted by rcgldr

I assume you mean almost sorted data in a linked list.

Yes, exactly.

Originally Posted by rcgldr

For a bottom up merge sort for linked lists, you'd only need 2 input pointers and 2 output pointers. The initial pass traverses the original list for "runs" (sequences of ascending values), sets the next pointers at the end of runs to NULL, then attaches the runs to the 2 output list pointers, alternating between them. Then merge passes are performed.

I think you are forgetting how important it is to the overall efficiency, that the merged lists are roughly the same size. (Or, to be more precise, that the "tree" is balanced. Just because there is no tree explicitly created, does not mean you can ignore it.)

Theoretical arguments are fun, but reality always trumps theory.

If you wish to sway minds, you need to show practical comparison.

The true test, in my opinion, is very simple. Generate some linked lists (integer keys are fine) with tunable randomness, then compare the time taken to sort them using the three functions. I'm mostly interested in longish lists, myself, say a nice million nodes; so I'd perhaps compose the list as N sorted lists concatenated, then test the different linked-list sorting approaches, measuring the run times, for various numbers of N, from say two to a hundred, emphasis on the low side. Then maybe see what happens if you add K random nodes into random places into the list.

If you can show that your bottom-up merge sort -- implemented without pointer bit tricks; we want the code to be maintainable and portable -- performs better than a straightforward top-down merge sort with the continuous pass as I outlined above, then I'm satisfied you have a valid point. Otherwise, I won't buy it.

Because you're the OP, it's your responsibility to prove your claims (assuming you want to). I can of course provide you a simple implementation of the continuous-run-scanning top-down merge sort, but I'm sure you can too, if you want.

Please do remember that I'm not questioning you or your skills or capabilities; I'm only trying to poke holes in your argument to see if it holds true or not.

rcgldr, you make more arguments, but don't back them up with data or facts.

I don't like that, so I decided to show you exactly how and why you are wrong.

(Since I use Linux, you will need to adjust the following to compile for Windows, but please do, and do post the modified code; it should be easy to fix. Since I don't have Windows, I can't do that for you.)

Here are the three sort functions I wanted to test. sort.c:

Code:

#include <stdlib.h>
#include "sort.h"

/*
 * Common helper functions.
*/

static node_t *merge2(node_t *list1, node_t *list2)
{
    node_t *root, *tail;

    if (!list2)
        return list1;
    if (!list1)
        return list2;

    if (list1->key <= list2->key) {
        root = tail = list1;
        list1 = list1->next;
    } else {
        root = tail = list2;
        list2 = list2->next;
    }

    while (list1 && list2)
        if (list1->key <= list2->key) {
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }

    if (list1)
        tail->next = list1;
    else
    if (list2)
        tail->next = list2;
    else
        tail->next = (node_t *)0;

    return root;
}

static node_t *merge3(node_t *list1, node_t *list2, node_t *list3)
{
    node_t *root, *tail;

    if (!list3)
        return merge2(list1, list2);

    if (list1->key <= list2->key) {
        if (list1->key <= list3->key) {
            root = tail = list1;
            list1 = list1->next;
        } else {
            root = tail = list3;
            list3 = list3->next;
        }
    } else {
        if (list2->key <= list3->key) {
            root = tail = list2;
            list2 = list2->next;
        } else {
            root = tail = list3;
            list3 = list3->next;
        }
    }

    while (list1 && list2 && list3)
        if (list1->key <= list2->key) {
            if (list1->key <= list3->key) {
                tail->next = list1;
                tail = list1;
                list1 = list1->next;
            } else {
                tail->next = list3;
                tail = list3;
                list3 = list3->next;
            }
        } else {
            if (list2->key <= list3->key) {
                tail->next = list2;
                tail = list2;
                list2 = list2->next;
            } else {
                tail->next = list3;
                tail = list3;
                list3 = list3->next;
            }
        }

    if (!list2) {
        list2 = list3;
        list3 = (node_t *)0;
    }
    if (!list1) {
        list1 = list2;
        list2 = list3;
        list3 = (node_t *)0;
    }

    while (list1 && list2)
        if (list1->key <= list2->key) {
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }

    if (list1)
        tail->next = list1;
    else
    if (list2)
        tail->next = list2;
    else
        tail->next = (node_t *)0;

    return root;
}

/*
 * Traditional top-down merge sort.
*/

node_t *do_topdown(node_t *list, const size_t size)
{
    if (size > 1) {
        const size_t half = size / 2;
        size_t       n = half - 1;
        node_t      *temp = list;
        node_t      *tail;

        /* Find split point (node before second half). */
        while (n-->0)
            temp = temp->next;

        tail = temp->next;
        temp->next = (node_t *)0;

        if (half > 1)
            list = do_topdown(list, half);

        if (size - half > 1)
            tail = do_topdown(tail, size - half);

        return merge2(list, tail);
    } else
        return list;
}

node_t *topdown_sort(node_t *list)
{
    node_t *head, *tail;
    size_t  size,  half = 0;

    /* Trivial list? */
    if (!list || !list->next)
        return list;

    /* Find list length and split point. */
    head = tail = list;
    while (tail && tail->next) {
        tail = tail->next->next;
        list = list->next;
        half++;
    }
    size = 2 * (half++);
    if (tail)
        size++;

    tail = list->next;
    list->next = (node_t *)0;

    return merge2(do_topdown(head, half), 
                  do_topdown(tail, size - half));
}

/*
 * Top-down sequence-scanning merge sort
*/

node_t *do_nominal(node_t *list, size_t size)
{
    if (size > 1) {
        node_t *prefix = list;
        node_t *left, *tail;
        size_t  prefixlen = 1;
        size_t  half;

        /* Find sorted prefix. */
        while (list->next && list->key <= list->next->key) {
            list = list->next;
            prefixlen++;
        }

        /* Already sorted? */
        if (!list->next)
            return prefix;

        left = tail = list->next;
        list->next = (node_t *)0;
        list = tail;
        size -= prefixlen;

        /* Single-node unsorted part? */
        if (size < 2)
            return merge2(prefix, left);

        /* Find split point. */
        half = size/2 - 1;
        while (half-->0)
            list = list->next;

        tail = list->next;
        half = size / 2;
        list->next = (node_t *)0;        

        /* Recurse and three-way merge. */
        return merge3(prefix, do_nominal(left, half), do_nominal(tail, size - half));

    } else
        return list;
}

node_t *nominal_sort(node_t *list)
{
    node_t *prefix, *left, *tail;
    size_t  size, half;

    /* Trivial list? */
    if (!list || !list->next)
        return list;

    /* Find sorted prefix. */
    prefix = list;
    while (list->next && list->key <= list->next->key)
        list = list->next;

    /* Already sorted? */
    if (!list->next)
        return prefix;

    /* Detach unsorted part from list. */
    left = list->next;
    list->next = (node_t *)0;
    list = tail = left;

    /* Single-node unsorted part? */
    if (!list->next)
        return merge2(prefix, left);

    /* Find split point in unsorted part. */
    half = 0;
    while (tail && tail->next) {
        tail = tail->next->next;
        list = list->next;
        half++;
    }
    size = 2 * (half++);
    if (tail)
        size++;
    tail = list->next;
    list->next = (node_t *)0;

    /* Recurse and three-way merge. */
    return merge3(prefix, do_nominal(left, half), do_nominal(tail, size - half));
}

/*
 * Nonrecursive bottom-up merge sort using 32 pointers.
*/
#ifndef PARTS
#define PARTS 32
#endif

node_t *bottomup_sort(node_t *list)
{
    node_t *part[PARTS] = { 0 };
    node_t *curr;
    size_t  i;

    while (list) {

        curr = list;
        list = list->next;
        curr->next = (node_t *)0;

        if (part[0]) {
            curr = merge2(part[0], curr);

            i = 1;
            while (i < PARTS - 1 && part[i]) {
                curr = merge2(part[i], curr);
                part[i-1] = (node_t *)0;
                i++;
            }
            part[i-1] = (node_t *)0;

            if (!part[i])
                part[i] = curr;
            else
                part[i] = merge2(part[i], curr);
            
        } else
            part[0] = curr;
    }

    i = 0;
    while (i < PARTS - 1 && !part[i])
        i++;

    while (i < PARTS - 1) {
        if (part[i+1])
            part[i+1] = merge2(part[i+1], part[i]);
        else
            part[i+1] = part[i];
        i++;
    }

    return part[PARTS-1];
}

Above, topdown_sort() is a traditional top-down merge sort, nominal_sort() is the top-down merge sort that detects continuous runs and uses three-way merging, and bottomup_sort() is my bottom-up merge sort implementation.

sort.h:

Code:

#ifndef   SORT_H
#define   SORT_H

#ifdef __cplusplus
extern "C" {
#endif

typedef struct node_st  node_t;
struct node_st {
    node_t  *next;
    long     key;
};

node_t  *topdown_sort(node_t *);
node_t  *nominal_sort(node_t *);
node_t *bottomup_sort(node_t *);

#ifdef __cplusplus
}
#endif

#endif /* SORT_H */

To measure the time taken by each, I use timing.h:

Code:

#ifndef   TIMING_H
#define   TIMING_H
#ifdef __cplusplus
extern "C" {
#endif

void timing_start();

void timing_stop(double *const wall_seconds,
                 double *const cpu_seconds,
                 double *const cpu_cycles);

#ifdef __cplusplus
}
#endif
#endif /* TIMING_H */

which in Linux and most POSIX systems can be implemented as timing.c:

Code:

#define _POSIX_C_SOURCE 199309L
#include <time.h>

#if defined(__GNUC__) && (defined(__x86_64__) || defined(__i386__))

static unsigned int  cycles_start[2];
static struct timespec wall_start;
static struct timespec  cpu_start;

void timing_start(void)
{
    clock_gettime(CLOCK_REALTIME, &wall_start);
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cpu_start);
    asm volatile ("rdtsc" : "=a" (cycles_start[0]), "=d" (cycles_start[1]));
} 

void timing_stop(double *const wall_seconds,
                 double *const cpu_seconds,
                 double *const cpu_cycles)
{
    unsigned int  cycles_stop[2];
    struct timespec wall_stop;
    struct timespec  cpu_stop;

    asm volatile ("rdtsc" : "=a" (cycles_stop[0]), "=d" (cycles_stop[1]));
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cpu_stop);
    clock_gettime(CLOCK_REALTIME, &wall_stop);

    if (cpu_cycles)
        *cpu_cycles = ((((long long)cycles_stop[1])  << 32) + (long long)cycles_stop[0])
                    - ((((long long)cycles_start[1]) << 32) + (long long)cycles_start[0]);

    if (wall_seconds)
        *wall_seconds = difftime(wall_stop.tv_sec, wall_start.tv_sec)
                      + (double)(wall_stop.tv_nsec - wall_start.tv_nsec) / 1000000000.0;

    if (cpu_seconds)
        *cpu_seconds = difftime(cpu_stop.tv_sec, cpu_start.tv_sec)
                     + (double)(cpu_stop.tv_nsec - cpu_start.tv_nsec) / 1000000000.0;
}

#else

static struct timespec wall_start;
static struct timespec  cpu_start;

void timing_start(void)
{
    clock_gettime(CLOCK_REALTIME, &realtime_start);
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cputime_start);
} 

void timing_stop(double *const wall_seconds,
                 double *const cpu_seconds,
                 long   *const cpu_cycles)
{
    struct timespec wall_stop;
    struct timespec  cpu_stop;

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cputime_stop);
    clock_gettime(CLOCK_REALTIME, &realtime_stop);

    if (cpu_cycles)
        *cpu_cycles = 0.0;

    if (wall_seconds)
        *wall_seconds = difftime(wall_stop.tv_sec, wall_start.tv_sec)
                      + (double)(wall_stop.tv_nsec - wall_start.tv_nsec) / 1000000000.0;

    if (cpu_seconds)
        *cpu_seconds = difftime(cpu_stop.tv_sec, cpu_start.tv_sec)
                     + (double)(cpu_stop.tv_nsec - cpu_start.tv_nsec) / 1000000000.0;
}

#endif

The above uses the x86/x86-64 RDTSC to measure the CPU cycles if possible; otherwise it uses zero for the cycle counts.

The benchmark.c:

Code:

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <stdio.h>
#include "timing.h"
#include "sort.h"

/* Xorshift random number generator.
*/
static uint32_t xorshift_state[4] = {
    123456789U,
    362436069U,
    521288629U,
    88675123U
};

static int xorshift_setseed(const void *const data, const size_t length)
{
    uint32_t state[4];

    if (length < 1)
        return ENOENT;

    if (length < sizeof state) {
        memset(state, 0, sizeof state);
        memcpy(state, data, length);
    } else
        memcpy(state, data, sizeof state);

    /* State cannot be all zeros, as that'd produce only zeros. */
    if (state[0] || state[1] || state[2] || state[3]) {
        memcpy(xorshift_state, state, sizeof state);
        return 0;
    }

    return EINVAL;
}

static uint32_t xorshift_u32(void)
{
    const uint32_t temp = xorshift_state[0] ^ (xorshift_state[0] << 11U);
    xorshift_state[0] = xorshift_state[1];
    xorshift_state[1] = xorshift_state[2];
    xorshift_state[2] = xorshift_state[3];
    return xorshift_state[3] ^= (temp >> 8U) ^ temp ^ (xorshift_state[3] >> 19U);
}

static uint64_t xorshift_u64(void)
{
    return ((uint64_t)xorshift_u32() << 32)
         |  (uint64_t)xorshift_u32();
}

static size_t xorshift_range(const size_t min, const size_t max)
{
    if (max > min) {
        const size_t size = max - min;
        size_t       mask = ~0;
        size_t       temp;

        while (mask / (size_t)2 > size)
            mask /= (size_t)2;
        mask--;        

        if (size < (size_t)4294967295.0) {
            do {
                temp = xorshift_u32() & mask;
            } while (temp > size);
            return temp + min;
        } else {
            do {
                temp = xorshift_u64() & mask;
            } while (temp > size);
            return temp + min;
        }
    } else
        return min;
}

/* Given an array of keys,
 * dynamically allocate a single block, and fill with nodes as
 * the corresponding linked list.
*/
node_t *linked_list(const int *const key, const size_t len)
{
    node_t *array;
    size_t  i;

    if (len < 1) {
        errno = 0;
        return (node_t *)0;
    }

    array = malloc(len * sizeof array[0]);
    if (!array) {
        errno = ENOMEM;
        return (node_t *)0;
    }

    for (i = 0; i < len; i++) {
        array[i].next = &array[i+1];
        array[i].key  = key[i];
    }

    array[len-1].next = (node_t *)0;

    return array;
}

size_t sorted_length(const node_t *node)
{
    size_t len = 1;

    if (!node)
        return 0;

    while (node->next) {
        if (node->key > node->next->key)
            return len;
        node = node->next;
        len++;
    }

    return len;
}

int parse_range(const char *const arg, size_t *const min, size_t *const max)
{
    long val1, val2;
    char dummy;

    if (!arg || !*arg)
        return EINVAL;

    if (sscanf(arg, " %ld - %ld %c", &val1, &val2, &dummy) == 2 ||
        sscanf(arg, " %ld : %ld %c", &val1, &val2, &dummy) == 2 ||
        sscanf(arg, " %ld .. %ld %c", &val1, &val2, &dummy) == 2) {
        if (val1 <= val2) {
            if (min) *min = val1;
            if (max) *max = val2;
        } else {
            if (min) *min = val2;
            if (max) *max = val1;
        }
        return 0;
    }

    if (sscanf(arg, " %ld + %ld %c", &val1, &val2, &dummy) == 2) {
        if (val2 >= 0L) {
            if (min) *min = val1;
            if (max) *max = val1 + val2;
        } else {
            if (min) *min = val1 + val2;
            if (max) *max = val1;
        }
        return 0;
    }

    if (sscanf(arg, " %ld %c", &val1, &dummy) == 1) {
        if (min) *min = val1;
        if (max) *max = val1;
        return 0;
    }

    return EINVAL;
}

int compare_doubles(const void *ptr1, const void *ptr2)
{
    const double val1 = *(const double *)ptr1;
    const double val2 = *(const double *)ptr2;

    if (val1 < val2)
        return -1;
    else
    if (val1 > val2)
        return +1;
    else
        return  0;
}

int main(int argc, char *argv[])
{
    size_t  sublists, sublists_min, sublists_max;
    size_t  length, length_min, length_max;
    size_t  sprinkles, sprinkles_min, sprinkles_max;
    size_t  repeats;

    size_t  len, max_len;
    int    *key;

    double *topdown_wall,   *nominal_wall,   *bottomup_wall;
    double *topdown_cpu,    *nominal_cpu,    *bottomup_cpu;
    double *topdown_cycles, *nominal_cycles, *bottomup_cycles;
    size_t  topdown, nominal, bottomup;

    node_t *list, *sorted;

    size_t  i, n;
    int     one;

    if (argc < 5 || argc > 6 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
        fprintf(stderr, "\n");
        fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
        fprintf(stderr, "       %s REPEATS SUBLISTS LENGTH SPRINKLES [ SEED ]\n", argv[0]);
        fprintf(stderr, "Where:\n");
        fprintf(stderr, "       REPEATS     Number of operations measured\n");
        fprintf(stderr, "       SUBLISTS    Number of sorted sublists\n");
        fprintf(stderr, "       LENGTH      Length of each sublist\n");
        fprintf(stderr, "       SPRINKLES   Number of added random elements\n");
        fprintf(stderr, "       SEED        String used to seed the Xorshift PRNG\n");
        fprintf(stderr, "\n");
        fprintf(stderr, "This program generates a linked list with the above\n");
        fprintf(stderr, "randomness properties, then measures the time taken\n");
        fprintf(stderr, "to sort it using different sorting approaches.\n");
        fprintf(stderr, "\n");
        return 1;
    }

    if (argc >= 5)
        if (xorshift_setseed(argv[4], strlen(argv[4]))) {
            fprintf(stderr, "%s: Cannot use string as a random number seed.\n", argv[4]);
            return 1;
        }

    {
        long value;
        char dummy;
        if (sscanf(argv[1], " %ld %c", &value, &dummy) == 1 && value > 0L) 
            repeats = value;
        else {
            fprintf(stderr, "%s: Invalid number of sort operations to measure.\n", argv[1]);
            return 1;
        }
    }
    topdown_wall    = malloc(repeats * sizeof topdown_wall[0]);
    topdown_cpu     = malloc(repeats * sizeof topdown_cpu[0]);
    topdown_cycles  = malloc(repeats * sizeof topdown_cycles[0]);
    nominal_wall    = malloc(repeats * sizeof nominal_wall[0]);
    nominal_cpu     = malloc(repeats * sizeof nominal_cpu[0]);
    nominal_cycles  = malloc(repeats * sizeof nominal_cycles[0]);
    bottomup_wall   = malloc(repeats * sizeof bottomup_wall[0]);
    bottomup_cpu    = malloc(repeats * sizeof bottomup_cpu[0]);
    bottomup_cycles = malloc(repeats * sizeof bottomup_cycles[0]);
    if (!topdown_wall  || !topdown_cpu  || !topdown_cycles ||
        !nominal_wall  || !nominal_cpu  || !nominal_cycles ||
        !bottomup_wall || !bottomup_cpu || !bottomup_cycles) {
        fprintf(stderr, "Not enough memory: too many repeats (%lu).\n", (unsigned long)repeats);
        return 1;
    }

    if (parse_range(argv[2], &sublists_min, &sublists_max) || sublists_max < sublists_min) {
        fprintf(stderr, "%s: Invalid number of sublists.\n", argv[2]);
        return 1;
    }

    if (parse_range(argv[3], &length_min, &length_max) || length_max < length_min) {
        fprintf(stderr, "%s: Invalid sublist length.\n", argv[3]);
        return 1;
    }

    if (parse_range(argv[4], &sprinkles_min, &sprinkles_max) || sprinkles_max < sprinkles_min) {
        fprintf(stderr, "%s: Invalid number of added random elements.\n", argv[4]);
        return 1;
    }

    sublists = xorshift_range(sublists_min, sublists_max);
    sprinkles = xorshift_range(sprinkles_min, sprinkles_max);

    max_len = (size_t)sublists * (size_t)length_max + (size_t)sprinkles;
    len = 0;

    key = malloc(max_len * sizeof key[0]);
    if (!key) {
        fprintf(stderr, "Not enough memory (for %lu sublists and %lu sprinkles).\n",
                        (unsigned long)sublists, (unsigned long)sprinkles);
        return 1;
    }

    for (n = 0; n < sublists; n++) {
        length = xorshift_range(length_min, length_max);
        for (i = 0; i < length; i++)
            key[len++] = 256*i + (xorshift_u32() & 255);
    }

    for (n = 0; n < sprinkles; n++) {
        i = xorshift_range(0, len);
        if (i < len)
            memmove(key + i + 1, key + i, (len - i) * sizeof key[0]);
        key[i] = xorshift_u32();
        len++;
    }

    if (len < 2) {
        fprintf(stderr, "Nothing to sort.\n");
        return 1;
    }

    topdown  = 0;
    nominal  = 0;
    bottomup = 0;

    list = NULL;

    while (topdown < repeats || nominal < repeats || bottomup < repeats) {
        one = (xorshift_u32() >> 16) & 3;
        if (!one)
            continue;

        if (!list) {
            list = linked_list(key, len);
            if (!list) {
                fprintf(stderr, "Out of memory!\n");
                return 1;
            }
        }

        if (topdown < repeats && one == 1) {

            timing_start();
            sorted = topdown_sort(list);
            timing_stop(&topdown_wall[topdown], &topdown_cpu[topdown], &topdown_cycles[topdown]);
            if (sorted_length(sorted) != len) {
                fprintf(stderr, "topdown_sort() failed.\n");
                return 1;
            }

            topdown++;
            free(list);
            list = NULL;

        } else
        if (nominal < repeats && one == 2) {

            timing_start();
            sorted = nominal_sort(list);
            timing_stop(&nominal_wall[nominal], &nominal_cpu[nominal], &nominal_cycles[nominal]);
            if (sorted_length(sorted) != len) {
                fprintf(stderr, "nominal_sort() failed.\n");
                return 1;
            }

            nominal++;
            free(list);
            list = NULL;

        } else
        if (bottomup < repeats && one == 3) {

            timing_start();
            sorted = bottomup_sort(list);
            timing_stop(&bottomup_wall[bottomup], &bottomup_cpu[bottomup], &bottomup_cycles[bottomup]);
            if (sorted_length(sorted) != len) {
                fprintf(stderr, "bottomup_sort() failed.\n");
                return 1;
            }

            bottomup++;
            free(list);
            list = NULL;
        }
    }

    qsort(topdown_wall,    repeats, sizeof topdown_wall[0],    compare_doubles);
    qsort(topdown_cpu,     repeats, sizeof topdown_cpu[0],     compare_doubles);
    qsort(topdown_cycles,  repeats, sizeof topdown_cycles[0],  compare_doubles);
    qsort(nominal_wall,    repeats, sizeof nominal_wall[0],    compare_doubles);
    qsort(nominal_cpu,     repeats, sizeof nominal_cpu[0],     compare_doubles);
    qsort(nominal_cycles,  repeats, sizeof nominal_cycles[0],  compare_doubles);
    qsort(bottomup_wall,   repeats, sizeof bottomup_wall[0],   compare_doubles);
    qsort(bottomup_cpu,    repeats, sizeof bottomup_cpu[0],    compare_doubles);
    qsort(bottomup_cycles, repeats, sizeof bottomup_cycles[0], compare_doubles);

    fprintf(stderr, "List length:  %lu nodes\n", (unsigned long)len);
    fprintf(stderr, "Sublists:     %lu\n", (unsigned long)sublists);
    fprintf(stderr, "Random nodes: %lu\n", (unsigned long)sprinkles);
    fprintf(stderr, "\n");

    fprintf(stderr, "Traditional top-down merge sort:\n");
    fprintf(stderr, "\t%15.9f seconds wall time minimum\n", topdown_wall[0]);
    fprintf(stderr, "\t%15.9f seconds CPU time minimum\n", topdown_cpu[0]);
    if (topdown_cycles[0])
        fprintf(stderr, "\t%15.0f CPU cycles minimum\n", topdown_cycles[0]);
    fprintf(stderr, "\t%15.9f seconds wall time median\n", topdown_wall[repeats/2]);
    fprintf(stderr, "\t%15.9f seconds CPU time median\n", topdown_cpu[repeats/2]);
    if (topdown_cycles[repeats/2])
        fprintf(stderr, "\t%15.0f CPU cycles median\n", topdown_cycles[repeats/2]);
    fprintf(stderr, "\n");

    fprintf(stderr, "Top-down sorted-scanning merge sort:\n");
    fprintf(stderr, "\t%15.9f seconds wall time minimum\n", nominal_wall[0]);
    fprintf(stderr, "\t%15.9f seconds CPU time minimum\n", nominal_cpu[0]);
    if (nominal_cycles[0])
        fprintf(stderr, "\t%15.0f CPU cycles minimum\n", nominal_cycles[0]);
    fprintf(stderr, "\t%15.9f seconds wall time median\n", nominal_wall[repeats/2]);
    fprintf(stderr, "\t%15.9f seconds CPU time median\n", nominal_cpu[repeats/2]);
    if (nominal_cycles[repeats/2])
        fprintf(stderr, "\t%15.0f CPU cycles median\n", nominal_cycles[repeats/2]);
    fprintf(stderr, "\n");

    fprintf(stderr, "Bottom up merge sort:\n");
    fprintf(stderr, "\t%15.9f seconds wall time minimum\n", bottomup_wall[0]);
    fprintf(stderr, "\t%15.9f seconds CPU time minimum\n", bottomup_cpu[0]);
    if (bottomup_cycles[0])
        fprintf(stderr, "\t%15.0f CPU cycles minimum\n", bottomup_cycles[0]);
    fprintf(stderr, "\t%15.9f seconds wall time median\n", bottomup_wall[repeats/2]);
    fprintf(stderr, "\t%15.9f seconds CPU time median\n", bottomup_cpu[repeats/2]);
    if (bottomup_cycles[repeats/2])
        fprintf(stderr, "\t%15.0f CPU cycles median\n", bottomup_cycles[repeats/2]);
    fprintf(stderr, "\n");

    fflush(stderr);

    printf("%lu %lu %lu  ", (unsigned long)len, (unsigned long)sublists, (unsigned long)sprinkles);
    printf("%.0f %.0f %.0f ", topdown_wall[0], topdown_cpu[0], topdown_cycles[0]);
    printf("%.0f %.0f %.0f  ", topdown_wall[repeats/2], topdown_cpu[repeats/2], topdown_cycles[repeats/2]);
    printf("%.0f %.0f %.0f ", nominal_wall[0], nominal_cpu[0], nominal_cycles[0]);
    printf("%.0f %.0f %.0f  ", nominal_wall[repeats/2], nominal_cpu[repeats/2], nominal_cycles[repeats/2]);
    printf("%.0f %.0f %.0f ", bottomup_wall[0], bottomup_cpu[0], bottomup_cycles[0]);
    printf("%.0f %.0f %.0f\n", bottomup_wall[repeats/2], bottomup_cpu[repeats/2], bottomup_cycles[repeats/2]);

    return 0;
}

Finally, here is the Makefile I use to compile and run some test cases:

Code:

CC	:= gcc
CFLAGS	:= -W -Wall -O3 -fomit-frame-pointer
LD	:= $(CC)
LDFLAGS := -lrt
PROGS	:= benchmark

.PHONY: all clean pure run

all: clean benchmark pure run

clean:
	rm -f *.o $(PROGS)

pure:
	rm -f *.o

%.o: %.c
	$(CC) $(CFLAGS) -c $^

benchmark: sort.o timing.o benchmark.o
	$(LD) $^ $(LDFLAGS) -o $@

run: benchmark
	@rm -f results
	./benchmark 100  5 2001 0
	./benchmark 100 10 10000 10

If you copy-paste the makefile, note that the indentation on the left must be a TAB, not spaces.

The above runs two test cases, with 10005 and 100010 nodes. The benchmark dynamically regenerates the same list to be sorted, and runs the sort functions in random order; and, each sort is measured a hundred times, and only the minimum and median times are reported. (I trust the median times, myself.)

The first test case is a 10005-element list composed of five 2001-element long sorted sublists. Median timings:

Code:

Traditional top-down merge sort:
        339 µs, 1015095 cycles

Nominal Animal's top-down sorted-scanning merge sort:
        112 µs,  333738 cycles

Bottom-up merge sort:
        228 µs,  680681 cycles

The second test case is a 100010-element list composed of ten 10000-element long sorted sublists, with 10 random nodes thrown in somewhere. Median timings:

Code:

Traditional top-down merge sort:
       5360 µs, 16040680 cycles

Nominal Animal's top-down sorted-scanning merge sort:
       3030 µs,  9061101 cycles

Bottom-up merge sort:
       3330 µs,  9951478 cycles

I can think of real-world use cases where such lists are typical. In the first case, the top-down variant with sorted-sequence scanning is twice as fast as the bottom-up (without). In the second case, the top-down variant is still faster, but only by about 9%. Still, if such datasets were typical, it would clearly make sense to use the top-down sorted-sequence scanning variant -- just like I originally stated.

Furthermore, the top-down variant is slower than the bottom-up variant, it's not catastrophically so; it takes only up to twice the time the bottom-up variant does. If you consider the difficulty of fully grasping the scheme in the bottom-up variant, the slower run-time may be offset by the much easier (and thus cheaper) maintenance.

I didn't care enough to check whether these are stable, but it should be obvious that the top-down ones can be easily made stable, even with the sorted-sequence scanning.

The above results fully back my assertion that there are cases where top-down merge sort approaches make sense, and are preferable over bottom-up merge sort variants.

Your initial statement,

Originally Posted by rcgldr

[top down merge sort is] not efficient

is therefore incorrect. The results show that there are sensible, real world datasets where a simple variant of the top down merge sort clearly beats a bottom-up approach.

You could still prove your point by modifying or rewriting the above bottomup_sort() without pointer tricks or architecture-specific hacks -- we want portable and maintainable code --, in such a way that your variant consistently beats my top-down variant. It does not necessarily have to be stable, as long as it is clearly possible to make it so, if someone cares enough; after all, I didn't bother enough to make sure my variant is stable, either.

Note that to prove your point (that there is no need for top-down merge sort variants at all), it is enough for us to show even one class of datasets to disprove you, whereas you need to show your solution holds for all datasets. So, be prepared to test your variant with multiple input parameters.

If you don't bother, you're just insisting others listen to your unbacked opinions. That's worthless, as opinions are as free as the wind is. Opinions are only interesting if the context and basis can also be discussed. So, it's your turn to put your code where your argument is.

If you want to, that is.

Originally Posted by rcgldr

... top down merge sort is ... not efficient

Originally Posted by Nominal Animal

example code, 3 programs

To make this a fair comparison, you need a 4th program or you need to modify the bottom up merge. Change the lines in the bottom up merge to merge in one run at a time instead of one node at a time, and then compare the times.

Code:

    while (list) {

        curr = list;                   /* change these lines to get a run */
        list = list->next;
        curr->next = (node_t *)0;

The warnings are harmless, and can be silenced with explicit casts to the target variable types.

Originally Posted by rcgldr

I made this change

Using very similar changes (adding temp and four lines of code at the start of the while loop),

Code:

node_t *bottomup_sort(node_t *list)
{
    node_t *part[PARTS] = { 0 };
    node_t *curr, *temp;
    size_t  i;

    while (list) {

        curr = list;
        while (list->next && list->key <= list->next->key)
            list = list->next;

        temp = list->next;
        list->next = (node_t *)0;
        list = temp;

        if (part[0]) {
            curr = merge2(part[0], curr);

            i = 1;
            while (i < PARTS - 1 && part[i]) {
                curr = merge2(part[i], curr);
                part[i-1] = (node_t *)0;
                i++;
            }
            part[i-1] = (node_t *)0;

            if (!part[i])
                part[i] = curr;
            else
                part[i] = merge2(part[i], curr);
            
        } else
            part[0] = curr;
    }

    i = 0;
    while (i < PARTS - 1 && !part[i])
        i++;

    while (i < PARTS - 1) {
        if (part[i+1])
            part[i+1] = merge2(part[i+1], part[i]);
        else
            part[i+1] = part[i];
        i++;
    }

    return part[PARTS-1];
}

all three sorts seem to be stable (according to tests I added to my copy of benchmark.c -- the list pointers are assigned in increasing addresses initially, so they can be checked when keys are equal).

Yet, there is still a class of inputs for which the top-down scanning sort is still faster.

If there are about 500 sublists, each with 50 to 100 sorted nodes, and about 1% of random nodes sprinkled in, I get

Code:

./benchmark 100 500 50-100 28
Constructed a list with 37582 nodes, 500 sublists, 28 random nodes.
List length:  37582 nodes
Sublists:     500
Random nodes: 28

Traditional top-down stable merge sort:
	    0.003297334 seconds wall time minimum
	    0.003294635 seconds CPU time minimum
	        9859830 CPU cycles minimum
	    0.003338460 seconds wall time median
	    0.003335976 seconds CPU time median
	        9982739 CPU cycles median

Top-down stable sorted-scanning merge sort:
	    0.003141621 seconds wall time minimum
	    0.003139022 seconds CPU time minimum
	        9394353 CPU cycles minimum
	    0.003179516 seconds wall time median
	    0.003177121 seconds CPU time median
	        9507317 CPU cycles median

Bottom up stable merge sort:
	    0.003297222 seconds wall time minimum
	    0.003294462 seconds CPU time minimum
	        9859129 CPU cycles minimum
	    0.003334290 seconds wall time median
	    0.003331613 seconds CPU time median
	        9970504 CPU cycles median

37582 500 28  0.003335976  0.003177121  0.003331613

The difference in median times is about five percent in that exact case.
(This inversion point is heavily CPU-dependent, so it'll occur with different parameters on your CPU.)

I am fully aware that for the vast majority of all possible random lists, the bottom-up approach is faster. It just does not matter: I've already agreed that if there is no information on the sortedness or other properties of a linked list, bottom-up merge sort is my choice.

My point is, because there are still linked list inputs where the top-down variant is still faster, your assertion that a bottom-up merge sort is always better, does not hold.

If you want to prove your assertion that "top-down merge sort is inefficient", then you need to provide it really is. In other words, show a bottom-up merge sort implementation that is always (aside from some single specific inputs) at least as efficient as the top-down approach.

---

To me, the interesting bit is why the bottom-up approach behaves poorly when compared to the top-down approach, for specific input properties.

For many changes in input randomness, the efficiency of the top-down and bottom-up approaches change in similar ways. For some -- the above one is not the only one, and probably depends on the CPU features, too --, we see these surprising inversions. They are not specific to one exact set of parameters, but occur in a small domain; so, it does not look like just a random occurrence.

To see this, you'll need to run a large number of tests with a wide range of input parameters, and look for interesting cases. When you see one, run another batch of tests around the interesting parameters, to see if it is just a random effect, and not a tendency. (Just having one input parameter set does not prove anything, because there are so many factors that affect the run time; but when you can vary the parameters and still get a similar result, it's not just a random occurrence.)

I wonder, is there a way to counteract that poor behaviour? I suspect it is an effect of having a longish sorted run merged with a nearly full "virtual tree" (list array), causing a cascade of inefficient merges to occur.

Since the bottom-up version is nonrecursive, adding a bit of state (to count the length of the sorted input run) is virtually free. If the sorted input runs are long enough, some sort of procedure on how to merge it to the "virtual tree" (list array) might work around this wart.

Furthermore, it might be possible to augment the bottom-up sort to not only detect sorted runs, but reversed runs also. One needs to prepend instead of append, and use < instead of <= for the comparisons, to keep stability. But, it might make efficient merging even more complicated...

Interesting stuff.