>How would patents have prevented him thinking about it ? I don't understand this logic.

It would mean he would need a license for every building block of an algorithm. It would have meant early (and vital) algorithm research bogged down by lawyers and lawsuits. You can't release a free implementation without a license and so the free software ecosystem may not have appeared at all (and we wouldn't even realize what we lost). Lastly, Knuth is a mathematician and he could have chosen any number of specialties; early lawyerization of algorithm research may have denied us all his input in the field.

Current software giants benefited greatly from free ideas and copied mercilessly off each other. Even now the tendency is to have broad and inclusive cross-licensing, leaving mostly young companies in the firing line. The things that never get built probably dwarf any measurable damage caused by patent litigation.