Sexual reproduction allows beneficial mutations to spread and recombine in a population much faster than asexual reproduction (yes, e.coli has conjugation, but it's nowhere near as powerful). A complex trait might require multiple mutations to support it-- a gene pool that's constantly mixed by sexual reproduction will have much higher chances of the combination arising than with asexual reproduction.

You can observe the same thing in genetic algorithms, where crossover ("sexual" reproduction / mixing of two candidates) is often performed because it creates more viable offspring than simple cloning with mutations.