Title borrowed from Feigel et al. .
Sex is costly. In an asexual population, all individuals bear offsprings, resulting in a higher growth rate than in a sexual population (two-fold cost of sex). Finding a partner is risky, costly in terms of energy and resources, and it results in sexual selection which may not always favor survival. Finally, in sexual populations each individual passes only 50% of its genetic make-up to their offsprings and, furthermore, genetic recombination could break-up alleles that are in an epitastic relationship with one another (they are advantageous when together, but once separated they may incur into fitness loss).
"The advantages of sexual reproduction stem from quite various roots. For instance, sex increases genetic variability by recombination of the parental chromosomes. It makes a population more resistant against many unpredictable threats, such as deleterious mutations, parasites, a fluctuating environment, or competing groups. It also optimizes the evolutionary search for the best gene combinations in a single individual (epistasis) ."Let's try an understand this better. Different alleles in the genome are not always independent, as they may affect fitness in conjunction, a mechanism called epistasis. For example, two alleles may be beneficial together, but their benefit may be lost when separated by a recombination event. Or, it could be the other way around, that a mutation arises under certain constraints, and it's not until paired with a second mutation that it becomes beneficial. This is often observed in drug resistance, for example. A mutation that confers the organism (a virus, or a bacterium) drug resistance could potentially make it less fit (for example, if it makes the organism more "visible" to the immune system). In these cases, often one observes a new mutation arise in conjunction with the drug-resistant one, and the two together restore the organism's original fitness. These secondary mutations are called compensatory mutations because they compensate for the original loss of fitness.
Recombination of genomes can go either way: it can bring beneficial mutations together, or, it can break them apart. In a Nature Genetics review , the authors mention a study done on segmented viruses: in this case, "sex" is equivalent to two viruses co-infecting the same cell, as when this happens the enzyme that replicates the genes jumps back and forth between the two genomes and the resulting new genome is a reshuffle of the two parental ones. The advantage of using viruses to study the effect of sex is that you can compare the result of sexual reproduction versus asexual reproduction in the same population. In the case of the segmented virus study, it was observed that an adverse mutation was slower to get cleared in the sexual population than the asexual one.
The same review cites studies done on yeast that yielded mixed results: some showed that sex did increase the rate of adaptation of the population, and some showed the opposite. A paradox? Not quite, if you throw into the picture the size of the population.
"Two recent studies have also tested the effect of recombination on the rate of adaptation in evolving microbial populations. When populations of C. reinhardtii that initially lacked genetic variation were allowed to adapt to a novel growth medium in sexual and asexual populations of varying size, sex increased the rate of adaptation at all population sizes, but particularly in large populations ."Another study done on sexual and asexual yeast strains, compared adaptation in two environments: the mouse brain, which represented a highly variable environment, and a test tube with minimal growth medium.
"When sex was induced, the sexual strain won the competition in the mouse brain but not in the test tube, despite the fact that it also showed general adaptation to this environment. These results indicate an advantage to sex during adaptation to variable or harsh environments ."Despite all these studies, it is still unclear what drove the evolution of sex. Did sex prevail thanks to epistasis? Or was it just drift, the random accumulation of mutations due to pure chance? More recent studies have looked at a combination of mechanisms that may have been responsible for the rise in sexual populations. For example, other aspects to account for, besides epistasis and drift, are redundancy and genome complexity. As organisms have evolved, their genomes have increased in size and complexity. Redundancy allows for more than one gene or pathway to have same function, buffering the effect of deleterious mutations. It also maintains a reservoir of non-coding allele variants that are always available in the search for new evolutionary pathways. At the same time, sex and recombination together cause genomes to be more robust and overcome the short-term disadvantage in favor of long-term advantages like increased evolvability.
 Alexander Feigel,, Avraham Englander,, & Assaf Engel (2009). Sex Is Always Well Worth Its Two-Fold Cost PLoS ONE DOI: 10.1371/journal.pone.0006012
 J. Arjan G. M. de Visser & Santiago F. Elena (2007). The evolution of sex: empirical insights into the roles of epistasis and drift Nature Genetics Review DOI: 10.1038/nrg1985