Unexpected Indexing performance (Everything's equal)
The table definition that you have is leading to some really odd optimizer behavior. I suspect that you're running into the issue documented in this SE post. To avoid that issue I'm going to create the table with just the [a] and the [IndexedPersisted] columns.

Query hints can be useful to figure out why the optimizer didn't pick the plan that you expected. Here you expected the index to be used but SQL Server did not use it. Let's view both query plans side by side:

SELECT *
FROM [dbo].[CompColIndexing]
ORDER BY [IndexedPersisted]
OPTION (MAXDOP 1);

SELECT *
FROM [dbo].[CompColIndexing] WITH (INDEX([IX_DJB_CompPersisted]))
ORDER BY [IndexedPersisted]
OPTION (MAXDOP 1);




The query optimizer thinks that the sort after the table scan is cheaper than 800000 RID lookups. Maybe it's wrong, so let's run the queries and compare performance metrics for them.

cpu_time    total_elapsed_time  logical_reads   reads
1204        1395                3087            1485
1516        1570                851798          0


I got those numbers by looking at sys.dm_exec_sessions after running the queries in separate sessions with "discard results after execution" checked so I wouldn't have to wait on the rows to be returned to the client.

Those numbers seem reasonable to me. Just because an index can be used does not mean that it should be used, especially if SQL Server will need to read the entire table by using the index. That's the worst use case for an index that I can think of. Indexes can be very useful when selecting a small percentage of rows from the table or when they are covering indexes.

The index is a covering one if I only select the [IndexedPersisted] column. In that case, SQL server thinks that using the index is cheaper than doing a table scan. Code to compare the two methods:

-- force table scan
SELECT [IndexedPersisted]
FROM [dbo].[CompColIndexing] WITH (INDEX(0))
ORDER BY [IndexedPersisted]
OPTION (MAXDOP 1);

SELECT [IndexedPersisted]
FROM [dbo].[CompColIndexing] WITH (INDEX([IX_DJB_CompPersisted]))
ORDER BY [IndexedPersisted]
OPTION (MAXDOP 1);




Here are the performance numbers:

cpu_time    total_elapsed_time  logical_reads   reads
1171        1212                2727            1088
343         406                 1798            0


Now that the index is a covering index it is a better access path for the table than a table scan.