Write a sorting program that looks erroneous but it is actually correct

Question

Write a program that sorts a vector of numbers (or any type of element) that looks like having one or more bugs, but it is actually ok.

• The code must be clear. Someone looking over the code must easily identify that it is a sort algorithm and must easily confuse a correct piece of code with a bug.
• The (apparent) bug can by anything that makes the code syntactically or semantically ill-formed (e.g. make the program not compile/run, exhibit UB when runned), make the program produce incorrect results, not terminate, or nondeterministic.
• The code must actually be well-formed and the program must deterministically produce the correct output in a finite time.
• The input can be hard coded in the program or can be read (from user, from file etc.).
• Input is considered valid and the program is not needed to verify input correctness.
• Any sorting algorithm is accepted. The data structure to hold the numbers is not needed to be an actual vector. The program can be designed to sort a variable number of numbers or a fixed number of numbers (e.g. a program to sort 3 numbers is ok). Sorting can be stable or not (note: a program designed to do a stable sort that has an apparent bug that makes the sort look unstable, but in actuality it is not a bug: the program actually does a stable sort — is a valid answer).
• you can call any functions (including sort functions) except 3rd party tools (unless they are widely spread and used e.g. boos for C++, JQuery for Javascript – those are ok to use)
• specify the language
• comment in code the part that looks like a bug.
• explain what the bug looks like doing wrong.
• explain (in a spoiler box) why it is actually not a bug.

This is a popularity contest. The answer with most votes wins.

---

This challenge is now over. The winner is @Clueless https://codegolf.stackexchange.com/a/30190/11400 with 8 votes. Thanks to all the submitters!

If you want to come in after the winner was awarded, please feel free to add a new answer. You are out of the race, but we are all interested to see interesting answers.

Answer 1

C++

Inspired by Apple's goto fail; bug.

#include <vector>
#include <map>
#include <iostream>

/**
 * Sorts a vector of doubles in reverse order using the bucket sort algorithm.
 */
std::vector<double> reverse_bucket_sort(const std::vector<double>& input) {
    // put each element into a bucket as many times as it appears
    std::map<double, int> bucket_counts;
    for (auto it : input)
        ++bucket_counts[it];

    std::vector<double> sorted_elements; // the return value

    // loop until we are done
    while (bucket_counts.size() > 0) {
        // find the largest element
        double maximum = std::numeric_limits<double>::lowest();
        for (auto it : bucket_counts) {
            if (it.first > maximum)
                maximum = it.first;
                maximum = it.first;
        }

        // add the largest element N times to our sorted vector
        for (int i = 0; i < bucket_counts[maximum]; ++i)
            sorted_elements.push_back(maximum);

        // and now erase the bucket
        bucket_counts.erase(maximum);
    }

    return sorted_elements;
}

int main(int argc, const char * argv[]) {
    std::vector<double> test_case = { 0, 1, 2.5, 10, 2.5, 2 };

    std::cout << "unsorted:";
    for (auto it : test_case) std::cout << " " << it;
    std::cout << std::endl;

    std::cout << "sorted:";
    for (auto it : reverse_bucket_sort(test_case)) std::cout << " " << it;
    std::cout << std::endl;

    return 0;
}

About halfway down the page there is a bug: we have a duplicate line after our if check! We are always going to update the maximum with whatever is the last value in bucket_count. Thankfully we are OK. In C++ std::map is sorted by keys. So we are just reversing the buckets, which is what we want.

Answer 2

Python2.x

import random
L = [random.randrange(20) for x in range(20)]
print "Unsorted:", L

def sort(L):
    # terminal case first. Otherwise sort each half recursively and combine
    return L.sort() if L > 1 else sort(L[:len(L)//2]) + sort(L[len(L)//2:])

sort(L)
print "Sorted:", L

Test run

list.sort returns None, so the part after the else is None + None. Luckily this doesn't cause a problem because the comparison of a list and and an int (L > 1) is always True. The function always returns None so we ignore the return value and Just print L which has been sorted in place Merging the sorted halves by catenation wouldn't have worked either even if the execution did get there.

Answer 3

C

Using sort incorrectly - on a 64 bit system int is 4 bytes and char * is 8 bytes, so shouldn't work.

Code:

#include <stdlib.h>
#include <stdio.h>

/* Compare integers to sort in reverse order */
int compare(const void *p, const void *q)
{
    const int *a = p;
    const int *b = q;

    return *b - *a;
}

int main()
{
    char *strings[] = {"B", "Que", "Ro", "Sum", "T"};
    int i;

    /* Let's use the integer compare to sort strings */
    qsort(&strings, sizeof(strings) / sizeof(char *), sizeof(char *), compare);

    /* Output the sorted results */
    for (i = 0; i < sizeof(strings) / sizeof(char *); i++)
        printf("%s\n", strings[i]);

    return 0;
}

Build:

$ gcc -o sort-no-sort sort-no-sort.c 

Run:

$ ./sort-no-sort 
T
Sum
Ro
Que
B

Yep, sorts okay!

Five things going on: 1) qsort passes pointers to integers, which are the same size as pointers to characters. 2) The strings are no more than four bytes in length (three + one terminator) = the size of an integer, which the sort routine happily treats as an integer. 3) Most compilers force alignment of data structures, so shorter strings take up the same space. Any larger though and be prepared for failures. 4) Endian-ness. 5) Zero initialization of internal bytes.

Answer 4

Cobra

class Program
    var _target as List<of bool?> = [true, true, false, true, true, nil, nil, false, true, nil, true]
    def main
        .sort(_target)
        print _target
    def sort(target as List<of bool?>)
        for i in target.count, for n, in target.count -1, if target[n] <> target[n + 1] and (target[n] or target[n + 1] == nil), target[n], target[n + 1] = target[n + 1], target[n]
            #should return sorted as [nil][false][true]

Oh dear, I appear to have incorrectly assigned n... and how did all those commas get there!?

When n is assigned the compiler assumes that it's being give the first half of a key-value pair (due to the comma), but there is no key-value pair so the compiler doesn't complain when it can't assign the second half of it to a non-existent variable. This results in n simply being given the key value.. which in this case is an index number. All of the other out-of-place-looking commas in the final line are actually part of standard Cobra syntax.

Answer 5

Java

public final class WeirdSort {
    public static void main(final String[] args) {

        //Random
        final Random random = new Random(441287210);

        //Some numbers:
        final List<Integer> list = new ArrayList<Integer>();
        list.add(9);
        list.add(11);
        list.add(3);
        list.add(5);
        list.add(7);

        //Sort randomly:
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(final Integer o1, final Integer o2) {
                return (o1 - o2) + random.nextInt(10);
            }
        });

        //Print
        for(final Integer i:list) {
            System.out.print(i + " ");
        }
    }
}

Prints: 3 5 7 9 11 

Works because this specific random value returns '1' for the first 10 results

Answer 6

Perl

Contractors these days! Don't they know that the <=> (a.k.a "spaceship") operator is only used for numeric sorting?

And why are they comparing operators?

How did this code even pass our stringent tests??!! It even uses strict and warnings!

use strict;
use warnings;

sub asciibetically { 0-($a lt $b) || 0+($a gt $b) || <=><=><=> }
                                                   #  ^  ^  ^
                                                   # What?? How did Perl even compile??!!

my @sorted = sort asciibetically qw( bravo charlie alpha );

print "@sorted";   # "alpha bravo charlie"
                   # And how come it works??!!

---

Why Perl compiles

The only real <=> operator is the one in the middle. The other two are just another way of writing glob("="). This means that <=><=><=> (nicknamed "space fleet") evaluates to 0.

---

Why it works

The asciibetically subroutine is an implementation of the string-comparing cmp operator: Binary "cmp" returns -1, 0, or 1 depending on whether the left argument is stringwise less than, equal to, or greater than the right argument.