Underhanded code contest: Not-so-quick sort The Task

Write a program, in the language of your choice, that reads lines of input from standard input until EOF, and then writes them to standard output in ASCIIbetical order, similar to the sort command-line program.  A short, non-underhanded example in Python is:

import sys

for line in sorted(sys.stdin):
    print(line.rstrip('\n'))


The underhanded part

Similar to The OS War, your goal is to prove that your favored platform is &ldquo;better&rdquo;, by having your program deliberately run much more slowly on a competing platform.  For the sake of this contest, a &ldquo;platform&rdquo; consists of any combination of:


Processor


Architecture (x86, Alpha, ARM, MIPS, PowerPC, etc.)
Bitness (64-bit vs. 32-bit vs. 16-bit)
Big- versus little-endian

Operating System


Windows vs. Linux vs. Mac OS, etc.
Different versions of the same operating system

Language implementation


Different compiler/interpreter vendors (e.g., MSVC++ vs. GCC)
Different versions of the same compiler/interpreter



Although you could meet the requirements by writing code like:

#ifndef _WIN32
    Sleep(1000);
#endif


Such an answer should not be upvoted.  The goal is to be subtle.  Ideally, your code should look like it's not platform-dependent at all.  If you do have any #ifdef statements (or conditions based on os.name or System.Environment.OSVersion or whatever), they should have a plausible justification (based on a lie, of course).

Include in your answer


The code
Your &ldquo;favorite&rdquo; and &ldquo;unfavorite&rdquo; platforms.
An input with which to test your program.
The running time on each platform, for the same input.
A description of why the program runs so slowly on the unfavorite platform.
C

CleverSort

CleverSort is a state-of-the-art (i. e. over-engineered and sub-optimal) two-step string sorting algorithm.

In step 1, it starts by pre-sorting the input lines using radix sort and the first two bytes of each line. Radix sort is non-comparative and works very well for strings.

In step 2, it uses insertion sort on the pre-sorted list of strings. Since the list is almost sorted after step 1, insertion sort is quite efficient for this task.

Code

#include &lt;stdint.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

// Convert first two bytes of Nth line into integer

#define FIRSTSHORT(N) *((uint16_t *) input[N])

int main()
{
    char **input = 0, **output, *ptemp;
    int first_index[65536], i, j, lines = 0, occurrences[65536];
    size_t temp;

    // Read lines from STDIN

    while(1)
    {
        if(lines % 1000 == 0)
            input = realloc(input, 1000 * (lines / 1000 + 1) * sizeof(char*));

        if(getline(&amp;input[lines], &amp;temp, stdin) != -1)
            lines++;
        else
            break;
    }

    output = malloc(lines * sizeof(char*));

    // Radix sort

    memset(occurrences, 0, 65536 * sizeof(int));

    for(i = 0; i &lt; lines; i++) occurrences[FIRSTSHORT(i)]++;

    first_index[0] = 0;

    for(i = 0; i &lt; 65536 - 1; i++)
        first_index[i + 1] = first_index[i] + occurrences[i];

    memset(occurrences, 0, 65536 * sizeof(int));

    for(i = 0; i &lt; lines; i++)
    {
        temp = FIRSTSHORT(i), output[first_index[temp] + occurrences[temp]++] = input[i];
    }

    // Insertion sort

    for(i = 1; i &lt; lines; i++)
    {
        j = i;

        while(j &gt; 0 &amp;&amp; strcmp(output[j - 1], output[j]) &gt; 0)
            ptemp = output[j - 1], output[j - 1] = output[j], output[j] = ptemp, j--;
    }

    // Write sorted lines to STDOUT

    for(i = 0; i &lt; lines; i++)
        printf("%s", output[i]);
}


Platforms

We all know that big-endian machines are much more efficient than their little-endian counterparts. For benchmarking, we'll compile CleverSort with optimizations turned on and create randomly a huge list (just over 100,000 strings) of 4-byte lines:

$ gcc -o cleversort -Ofast cleversort.c
$ head -c 300000 /dev/zero | openssl enc -aes-256-cbc -k '' | base64 -w 4 &gt; input
$ wc -l input
100011 input


Big-endian benchmark

$ time ./cleversort &lt; input &gt; /dev/null

real    0m0.185s
user    0m0.181s
sys     0m0.003s


Not too shabby.

Little-endian bechmark

$ time ./cleversort &lt; input &gt; /dev/null

real    0m27.598s
user    0m27.559s
sys     0m0.003s


Boo, little Endian! Boo!

Description

Insertion sort is really rather efficient for almost-sorted lists, but it is horribly inefficient for randomly sorted ones.

CleverSort's underhanded part is the FIRSTSHORT macro:

#define FIRSTSHORT(N) *((uint16_t *) input[N])


On big-endian machines, ordering a string of two 8-bit integers lexicographically or converting them to 16-bit integers and ordering them afterwards yields the same results.

Naturally, this is possible on little-endian machines as well, but the macro should have been

#define FIRSTSHORT(N) (input[N][0] | (input[N][1] &gt;&gt; 8))


which works as expected on all platforms.

The "big-endian benchmark" above is actually the result of using the proper macro.

With the wrong macro and a little-endian machine, the list is pre-sorted by the second character of every line, resulting in a random ordering from the lexicographical point of view. Insertion sort behaves very poorly in this case.