Cormen Edition 3 Exercise 23.2 Question 6 (Page No. 637)

Question

Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?

Answer 1

In this scenario kruskal's algorithm will run faster than prim's. The time complexity of kruskal's algorithm is

O(E log E) <--(time taken to sort E edges)      +    (E α(V)) <--  find set and union operations

Given that edge weights are uniformly distributed over half open interval [0,1), we can sort the edge list in O(E) time using bucket sort (see CLRS Bucket sort). 

So now the running time of kruskal's MST algorithm will become

O(E) + (E α(V))

where α(V) is the inverse ackermann function whose value is less than 5 for any practical input size 'n'. (ref wiki)

so, the running time of kruskal's MST algorithm is linear, where prim's will still work in O((V+E)log V)