Does anyone see anything wrong with this code? It sorts okay, but its taking longer than I'd expect. It's supposed to be an O(N Log-N) algorithm
( Read more... )
"This is java code. Quickly looking at it I think he/she needs to use quicksort algorithms to speed it up. I think there are such algorithms available in Java like Arrays.sort(char[ ]) 10:22 Have he/she do a Google search on speeding up sorts with quicksort algorithms in Java."
Unfortunately he couldn't spend alot of time looking at it for you.
Thanks. That would normally be correct, except that in this case I'm specifically studying the efficiency of the Merge Sort alorithm.
Turns out the problem may have been with declaring (and thus, in Java, initialzing) the temporary array within the merge method, which makes it happen repeatedly. I'm going to try it again without doing that.
Although I'm not certain, because even if initalizing the array take O(N) time, merge is already a O(N) algorithm, so I'd think that would only change the slope, not the shape of the curve. But I'm going to give it a try.
Comments 4
Reply
"This is java code. Quickly looking at it I think he/she needs to use quicksort algorithms to speed it up.
I think there are such algorithms available in Java like Arrays.sort(char[ ])
10:22 Have he/she do a Google search on speeding up sorts with quicksort algorithms in Java."
Unfortunately he couldn't spend alot of time looking at it for you.
Reply
Turns out the problem may have been with declaring (and thus, in Java, initialzing) the temporary array within the merge method, which makes it happen repeatedly. I'm going to try it again without doing that.
Although I'm not certain, because even if initalizing the array take O(N) time, merge is already a O(N) algorithm, so I'd think that would only change the slope, not the shape of the curve. But I'm going to give it a try.
Reply
Constructing an array must be time-consuming in Java.
Reply
Leave a comment