Recursive SQL CTE's and Custom Sort Ordering

Question

Image you are creating a DB schema for a threaded discussion board. Is there an efficient way to select a properly sorted list for a given thread? The code I have written works but does not sort the way I would like it too.

Let's say you have this data:

ID   |  ParentID
-----------------
1    |   null
2    |   1
3    |   2
4    |   1
5    |   3

So the structure is supposed to look like this:

1
|- 2
|  |- 3
|  |  |- 5
|- 4

Ideally, in the code, we want the result set to appear in the following order: 1, 2, 3, 5, 4
PROBLEM: With the CTE I wrote it is actually being returned as: 1, 2, 4, 3, 5

I know this would be easy to group/order by using LINQ but I am reluctant to do this in memory. It seems like the best solution at this point though...

Here is the CTE I am currently using:

with Replies as (   
    select c.CommentID, c.ParentCommentID 1 as Level
        from Comment c
        where ParentCommentID is null and CommentID = @ParentCommentID

    union all

    select c.CommentID, c.ParentCommentID, r.Level + 1 as Level
       from Comment c
       inner join Replies r on c.ParentCommentID = r.CommentID
)

select * from Replies

Any help would be appreciated; Thanks!

---

I'm new to SQL and had not heard about hierarchyid datatype before. After reading about it from this comment I decided I may want to incorporate this into my design. I will experiment with this tonight and post more information if I have success.

---

Update
Returned result from my sample data, using dance2die's suggestion:

ID  |  ParentID  | Level  | DenseRank
-------------------------------------
15     NULL          1         1
20     15            2         1
21     20            3         1
17     22            3         1
22     15            2         2
31     15            2         3
32     15            2         4
33     15            2         5
34     15            2         6
35     15            2         7
36     15            2         8

Answer 1

I am sure that you will love this. I recently find out about Dense_Rank() function, which is for "ranking within the partition of a result set" according to MSDN

Check out the code below and how "CommentID" is sorted.

As far as I understand, you are trying to partition your result set by ParentCommentID.

Pay attention to "denserank" column.

with Replies (CommentID, ParentCommentID, Level) as 
(
        select  c.CommentID, c.ParentCommentID, 1 as Level
        from    Comment c
        where   ParentCommentID is null and CommentID = 1

        union all

        select  c.CommentID, c.ParentCommentID, r.Level + 1 as Level
        from    Comment c
                inner join Replies r on c.ParentCommentID = r.CommentID
)
select  *,
        denserank = dense_rank() over (partition by ParentCommentID order by CommentID)
from    Replies
order by denserank

Result below

Answer 2

You have to use hierarchyid (sql2008 only) or a bunch of string (or byte) concatenation.