[CST-2] Kolmogorov complexity - cost of sorting

[Tom Puverle]

> For numbers and strings, no. For some other data type, perhaps, but I
> can't think of any offhand... Tom?

Almost any user defined data type will need to be sorted by comparison by
pair.
E.g. an example in C/C++ (I mean it's not quite C but not quite C++ either
:) )

	struct Point3D
	{
		int x,y;
	};

	...

	Point3D Vertices[1000 * 1000];	//create an interesting image
							//show to Neil Dodgson

	...
	//now sort the points, on these criteria:
	//increasing x BUT decreasing y
	//this is just a different total order
	//on the 2-tuples

	bool Point1BeforePoint2( Point3D * p1, Point3D * p2 )
	{
		return (p1->x < p2->x) ||	//x coordinate is greater
			(p1->x == p2->x && p1->y > p2->y );	//if the x coordinates
							//are the same, compare the y's

	}

I believe James' method couldn't cope with this ( and in fact with a
countably infinite set of others)

Tom