Sørensen debutó con la selección sub-19 de en 1993 y debutó con la selección sub-21 a sus 17 años en septiembre de ese mismo año.