Difference between revisions of "Talk:TADM2E 4.4"

From Algorithm Wiki
Jump to: navigation, search
(Created page with "Why break up the pairs and use buckets? It seems like you simply need three passes: First pass - get the reds and insert them in order into a new array of size n (assuming w...")
(No difference)

Revision as of 14:26, 7 January 2015

Why break up the pairs and use buckets? It seems like you simply need three passes: First pass - get the reds and insert them in order into a new array of size n (assuming we can use additional space) Second pass - get the blues and insert them in order into the array Third pass - get the yellows and insert them in order into the array

Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).