INSERT INTO .. SELECT nextval() ORDER BY - returns unexpectedly ordered values

It seems I have found a bug in the way postgres combines sequences and
ORDER BY with internal data ordering.

I have a table that has an `id`, where values were inserted somewhat
randomly. I wanted to re-order the rows a assign a new `id`, so I created a
sequence and did INSERT INTO .. SELECT. What I didn't understand is the
rows came out ordered correctly, but the new id's didn't. Instead of
incrementing correctly they seemed to follow the original ordering of the
rows.

I have reduced this to the following testcase:

CREATE TABLE test (
name character varying(4),
id smallint NOT NULL
);
CREATE TABLE test2 (like test);
ALTER TABLE test2 ADD old_id smallint;

INSERT INTO test VALUES ('c', 13);
INSERT INTO test VALUES ('d', 14);
INSERT INTO test VALUES ('a', 11);
INSERT INTO test VALUES ('b', 12);

CREATE TEMPORARY SEQUENCE tmp START 1;
INSERT INTO test2 SELECT name, nextval('tmp'), id FROM test ORDER BY id ASC;

SELECT * FROM test2;

What I expected:

name id old_id
a 1 11
b 2 12
c 3 13
d 4 14

What I got:

name id old_id
a 3 11
b 4 12
c 1 13
d 2 14

I have worked around this by clustering the old table on the new id before
SELECTing but this behavior doesn't seem to be documented, is this a bug?

Thanks,
Sjon