You don't have to think about the physical image sensors as just an array of sensors with 1:1 correspondence in the final picture. There was always a lot of computation in between - bayer filters with more green pixels, different grid patterns, multiple sensors per pixel, more pixels on the sensor than in the actual photo and so on.

Recent sensors have AF phase-detect sensors built into the image sensor, by splitting one "pixel" into two sensors (and having lots of them; sometimes in Canon sensors more than half of the pixels have this functionality; on some cameras you can extract the raw image including the different data on those pixels for bigger resolution). The difference between phase detect and contrast being that a phase-detect sensor will give exact values on how to adjust the focus, whilst contrast detection needs focus hunting in small adjustments, so it's slower.