Phasing genotypes to haplotypes is becoming increasingly important due to its applications in the study of diseases, population and evolutionary genetics, imputation, and so on. Several studies have focused on the development of computational methods that infer haplotype phase from population genotype data. The aim of this study was to compare phasing algorithms implemented in Beagle, Findhap, Flmpute, Impute2, and Shapelt2 software using 50k and 777k (HD) genotyping data. Six scenarios were considered: no-parents, sire-progeny pairs, sire-dam-progeny trios, each with and without pedigree information in Holstein cattle. Algorithms were compared with respect to their phasing accuracy and computational efficiency. In the studied population, Beagle and Flmpute were more accurate than other phasing algorithms. Across scenarios, phasing accuracies for Beagle and Flmpute were 99.49-99.90% and 99.44-99.99% for 50k, respectively, and 99.90-99.99% and 99.87-99.99% for HD, respectively. Generally, Flmpute resulted in higher accuracy when genotypic information of at least one parent was available. In the absence of parental genotypes and pedigree information, Beagle and Impute2 (with double the default number of states) were slightly more accurate than Flmpute. Findhap gave high phasing accuracy when parents' genotypes and pedigree information were available. In terms of computing time, Findhap was the fastest algorithm followed by Flmpute. Flmpute was 30 to 131, 87 to 786, and 353 to 1,400 times faster across scenarios than Beagle, Shapelt2, and Impute2, respectively. In summary, Flmpute and Beagle were the most accurate phasing algorithms. Moreover, the low computational requirement of Flmpute makes it an attractive algorithm for phasing genotypes of large livestock populations.