Selecting records in order of parent id

For a simple, perhaps suboptimally-scalable solution, I recommend hard-coding this with the maximum number of levels you will have:

For 2 levels only:

SELECT p2.name as `Parent name`, p1.*
FROM categories p1
LEFT JOIN categories p2 on p1.categories_id = p2.id

You're really asking about sorting, so I'd recommend generating a "path"-like string: (see below for sample output of this query)

SELECT Concat(If(isnull(p2.name),"",Concat("/",p2.name)),"/",p1.name) as `generated path`, p2.name as `Parent name`, p1.*
FROM categories p1
LEFT JOIN categories p2 on p1.parent_id = p2.id
order by `generated path`

For 3 levels, though your data doesn't have this yet -- path omitted because it will get ugly :)

SELECT p3.name as `Grandparent name`, p2.name as `Parent name`, p1.*
FROM categories p1
LEFT JOIN categories p2 on p1.categories_id = p2.id
LEFT JOIN categories p3 on p2.categories_id = p3.id

A more comprehensive solution for quickly selecting all items in a particular category at any level, which does require some work on all writes, is implementing a 'right' and 'left' numbering concept. But, further discussion on that is almost certainly going beyond the scope of what you're asking. However, that's the only good way in my experience to make this kind of self-referencing table very useful if it's going to get big (maybe after 1000+ rows with 3 to 10 levels).

Addendum: sample output from the second query:

generated path         Parent name         id         name         parent_id
----------------------------------------------------------------------------
/apple                                      1         apple                0
/apple/lisa                  apple          5         lisa                 1
/apple/mac                   apple          2         mac                  1
/atari                                      3         atari                0
/atari/st                    atari          4         st                   3

If those with no parents had null in their parent column, your statement would be very simple:

SELECT id, name, parent FROM categories order by coalesce(parent, id), id;

If you insist on 0 representing no parent, you can use more verbose CASE WHEN ... THEN ... statement.

Edit:

-- Sorting by name instead
select a.id, a.name, a.parent 
from categories a left join categories b on a.parent=b.id 
order by coalesce(b.name, a.name), a.name

This would work, but not recursively.

SELECT 
  b.* 
FROM
  categories a 
  RIGHT JOIN categories b ON b.parent = a.id
ORDER BY
  COALESCE(a.name, b.name), b.name

See if this works:

SELECT Table1.ID, Table1.name, Table1.parent, Table1_1.name, Table1_1.parent
FROM Table1 INNER JOIN Table1 AS Table1_1 ON Table1.ID = Table1_1.parent
ORDER BY Table1.name;

I built this with Micorsoft Access and it looked like what you wanted to me. I think you need a report to group on to visually give you what you want to give to a consumer, but for the sake joining correctly to get to that point this works.