I know that the fastest sort has O(n*log(n)) but I can't figure out what it is!(adsbygoogle = window.adsbygoogle || []).push({});

Here's what I have...

Use a tree structure: place the first value in the tree. If the next is less than the first, move the first to a child position and place the next in the main position. Otherwise just put the next in the child position. Basically repeat this for every item, with every Node having two children, always moving higher values downwards.

When all values are placed in the list, start taking them off.

remove element 1, and then check which of it's children are highest: move that child up and do the same computation for the now empty node: repeat until you hit a node with no children. Then remove element 1 again...

So... that comes out to:

O(n) items added * O(log[2](n)) sorting new items into heap

O(n) items removed * O(log[2](n)) sorting new items out of heap

That comes to:

O(2*log[2](n)*n)

Is that it? How do they eliminate the 2?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Fastest sort method?

**Physics Forums | Science Articles, Homework Help, Discussion**