bool
compare(int a, int b) {
	static int salt = (int)(rand()) << 16 | rand();
	static int bit = rand() % 20 + 6;	// Младшие биты сами по себе не случайные
							// Старшие биты тоже на фиг на всякий случай
	return (bool)((a * b * salt) & (2 ^ bit));
}

unsigned rand_seed;

unsigned rand2()
{
    __asm
    {
        rdtsc
        xor eax, rand_seed
        imul eax, 1664525ul
        add eax, 1013904223ul
        mov rand_seed, eax
    }
}

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

bool compare(int, int) {return (bool)(rand() % 2);}

void
main() {
	vector<int> v;

	srand(time(NULL));

	v.resize(20);

	for (int i = 0; i < v.size(); i++)
		v[i] = i;

	sort(v.begin(), v.end(), compare);

	for (i = 0; i < v.size(); i++)
		cout << v[i] << " ";

	cout << endl;
}

6 14 12 11 13 15 4 3 2 18 5 0 7 8 10 9 1 16 17 19

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace ::std;

typedef pair<int, int> item;
bool compare(const item &a, const item &b) {return a.second > b.second;}

int _tmain(int argc, _TCHAR* argv[])
{
    vector<item> v;
    srand(time(NULL));

    v.resize(20);

    for (int i = 0; i < v.size(); i++)
    {
        v[i].first = i;
        v[i].second = rand();
    }

    sort(v.begin(), v.end(), compare);

    for (i = 0; i < v.size(); i++)
        cout << v[i].first << " ";

    cout << endl;
    return 0;
}