DEV Community

Discussion on: Bubble Sort In JavaScript

Collapse
 
joshhadik profile image
Josh Hadik

Unfortunately there aren’t any green solutions for sorting an array.

This seems kind of inefficient at first but if you think about it it kind of makes sense. Best case scenario an array is already sorted, which logically still takes N steps since you have to walk through each element of the array to know it’s sorted.

But usually the array won’t be sorted, which means you still have to take N steps, plus even more steps to actually do the work of sorting the array, which is where we get second N in O(N2).

You can do better than N2 by using certain algorithms like merge sort, but even then you’re still limited by the fact that you have to touch every element at least once, plus you have to take extra steps to reorganize the content of the array, and it turns out the most efficient way you can do this is in O(N log N) time.