Returning Range Of Records From SQL Server 7 - Old Issue Revisited

Hi all,
I am using the following stored procedure in SQL 7 to return a range of records.

CREATE PROCEDURE spRetMyTable
@maxRows int, @lastRecord int, @SortPhrase varchar(122)
AS
begin
DECLARE @stSql VARCHAR(255)
SET ROWCOUNT @maxRows
SET @stSql = 'SELECT * FROM (SELECT TOP 10 colPrimary, col1, col2, col3 FROM (SELECT TOP ' + CONVERT(VARCHAR, @lastRecord) +
    'colPrimary, col1, col2, col3 FROM [MyTable] ORDER BY [colPrimary] ASC) AS tbl1 ORDER BY [colPrimary] DESC) AS tbl2 ORDER by [colPrimary] ASC'
exec(@stSql)
set rowcount 0
end
To execute the above procedure I am issuing the command:
execute spRetMyTable @maxRows 10, @lastRecord 1500
The column [colPrimary] is the primary field in the table.
I will be using the selected records in a gridView with paging (3 records per page). So if the next page is selected I would require to take out record 1491 to record 1494 and Add record 1501 to record 1503 in the datatable subject to the availability of records in the table MyTable.
How do I provide sorting by col1, col2 or col3? It could be single column or multiple column sorting as chosen by the user during runtime.

Is there any performance overhead in the above method in the first place?
Could it be improved by any alternative process?
I need YOUR ASSISTANCE to cater to the above issues in a feasible way.
Thanks in advance.