Using first-principle Hybrid-Monte-Carlo (HMC) simulations, we carry out an unbiased study of the competition between spin-density wave (SDW) and charge-density wave (CDW) order in the extended Hubbard model on the two dimensional hexagonal lattice at half filling. We determine the phase diagram in the space of on-site and nearest-neighbor couplings $U$ and $V$ in the region $V<U/3$, which can be simulated without a fermion sign problem, and find that a transition from semimetal to a SDW phase occurs at sufficiently large $U$ for basically all $V$. Tracing the corresponding phase boundary from $V=0$ to the $V=U/3$ line, we find evidence for critical scaling in the Gross-Neveu universality class for the entire boundary. With rather high confidence we rule out the existence of the CDW ordered phase anywhere in the range of parameters considered. We also discuss several improvements of the HMC algorithm which are crucial to reach these conclusions, in particular the improved fermion action with exact sublattice symmetry and the complexification of the Hubbard-Stratonovich field to ensure the ergodicity of the algorithm.