The first step in the coherent control of a photoinduced binary reaction is bond making or photoassociation. We have recently demonstrated coherent control of bond making in multi-photon femtosecond photoassociation of hot magnesium atoms, using linearly chirped pulses [Levin et al., arXiv:1411.1542]. The detected yield of photoassociated magnesium dimers was enhanced by positively chirped pulses which is explained theoretically by a combination of purification and chirp-dependent Raman transitions. The yield could be further enhanced by pulse optimization resulting in pulses with an effective linear chirp and a sub-pulse structure, where the latter allows for exploiting vibrational coherences. Here, we systematically explore the efficiency of phase-shaped pulses for the coherent control of bond making, employing a parametrization of the spectral phases in the form of cosine functions. We find up to an order of magnitude enhancement of the yield compared to the unshaped transform-limited pulse. The highly performing pulses all display an overall temporally increasing instantaneous frequency and are composed of several overlapping sub-pulses. The time delay between the first two sub-pulses almost perfectly fits the vibrational frequency of the generated intermediate wavepacket.These findings are in agreement with chirp-dependent Raman transitions and exploitation of vibrational dynamics as underlying control mechanisms.