Sorting by related tables

I have a few beginner questions about using related tables for
sorting.

create table region {
id SERIAL PRIMARY KEY,
name text,
-- order this table should be sorted in
-- a "1" is the top sort level
sort_order integer
);

create table city {
id SERIAL PRIMARY KEY,
name text,
region integer REFERENCES region
);

I want a way to adjust the sort order of the "region" table ("move
item up" or "move item down" in a web interface) without requiring
knowledge of the existing "sort_order" for the rows in the region
table. (i.e. requiring them to already be in an order).

Here's my "move up" (which is a lower sort_order value) statement.
(__TABLE__ is "region" and ? are $\d bind parameters)

UPDATE __TABLE__
SET sort_order =
CASE
-- subtract one from the item's sort, unless it's already "1"
WHEN id = ? AND sort_order > 1 THEN sort_order-1

-- for other items that are greater or equal to sort-1
WHEN id != ? AND sort_order >= (select sort_order from __TABLE__ where id = ?)-1
THEN sort_order+1

-- all others, leave alone
ELSE sort_order
END;

This works reasonably well for small tables, but doesn't scale and the
logic likely has holes. And behavior when adding new rows to the
region table is not defined.

1) How do most people do this? Use linked lists?

create table region {
id SERIAL PRIMARY KEY
name text,
list_head boolean, -- flag if this is the head of the linked list
next integer REFERENCES region
);

2) As a SQL beginner, I'm not seeing how to display rows from "city"
sorted in order based on the order in the "region" table.

3) Oh, and I have also this for checking IF there are items in
"region" that are "above" the item in question -- to see IF an item
can or cannot be moved up in the sort order relative to others.

SELECT id FROM __TABLE__
WHERE
sort_order <= (SELECT sort_order FROM __TABLE__ WHERE id = ?)
AND id != ?;

If that returns any rows then I know I can call the UPDATE to move the
item up.

Again, a very basic question: What method should be used to be sure
that nothing changes between the SELECT and the UPDATE?

--
Bill Moseley
moseley(at)hank(dot)org