T-SQL (SS2K8) :: Getting Minimum And Maximum Values In A Large Table

Table definition:

Create table code (
id identity(1,1)
code
parentcode
internalreference)

There are other columns but I have omitted them for clarity.

The clustered index is on the ID.

There are indexes on the code, parentcode and internalreference columns.

The problem is the table stores a parentcode with an internalreference and around 2000 codes which are children of the parentcode. I realise the table is very badly designed, but the company love orms!!

Example:
ID| Code| ParentCode| InternalReference|
1 | M111| NULL | 1|
2 | AAA | M111 | 2|
3 | .... | .... | ....|
4 | AAB | M111 | 2000|
5 | M222 | NULL | 2001|
6 | ZZZ | M222 | 2002|
7 | .... | .... | .... |
8 | ZZA | M222 | 4000|

The table currently holds around 300 millions rows.

The application does the following two queries to find the first internalreference of a code and the last internal refernce of a code:

--Find first internalrefernce
SELECT TOP 1 ID, InternalReference
FROM code
WHERE ParentCode = 'M222'
Order By InternalReference

-- Find last ineternalreference
SELECT TOP 1 ID, InternalReference
FROM code
WHERE ParentCode = 'M222'
Order By InternalReference DESC

These queries are running for a very long time, only because of the sort. If I run the query without the sort, then they return the results instantly, but obviously this doesn't find the first and last internalreference for a parentCode.

I realize the best way to fix this is to redesign the table, but I cannot do that at this time.

Is there a better way to do this so that two queries which individually run very slowly, can be combined into one that is more efficient?