Why do we need this check once again as we have already doing it in the while loop.
if (input[j] > key)