On disks, you have inter-symbol interference due to overlap of analog signal peaks. PRML uses digital filtering to handle this. It then uses various other signal processing algorithms, combined with maximum likelihood data detection to figure out what the most likely sequence of bits was that it just read from the disk. As you would imagine, this is some pretty hairy shit to analyze the complexity of if you want to try to say it's deterministic, because reading the same bits twice, even from the same starting position, will quite possibly give you two slightly different analog signals to analyze, etc. In reality, when you get down to it, it's non-deterministic in the average case because you end up having to include probability in the calculations.
Worst case is much easier, and is deterministic, because there is no probability involved.
Error correction codes can take care of the rest. No, it's not. You still have to get your damn file off the disk. He was timing a sorting program in it's entirety, not the sort. The bottleneck is only sort time in the shorter case because the worst case disk time never gets factored in, since it happens so infrequently in practice.