[Java + C] Merge Sort - Tilted Forum Project Discussion Community

feelgood · 02-10-2004, 08:15 PM

Why is it that when I looked at the merge sort source code provided by several sorting alogrithms websites that contains a "Thread.sleep(something)" which whenever I use it, the merge sorter actually runs longer than insertion, selection or even bubble!

So, when I removed the Thread.sleep() part, the merge sort alogrithms just zip by as if it was never there while the thread.sleep is still there, it runs like its a friggin turttle...

I know its because of the Thread.sleep() but comon, why is it even there in the first place??

n0nsensical · 02-10-2004, 08:29 PM

I have no idea...if you're trying to make a fast sort the last thing you want to do is take it off the CPU completely. The only thing I can think of is that the sort could take a long time...and that could be bad on an OS with cooperative multitasking?!?! Does Java even run on any of those?

feelgood · 02-10-2004, 08:54 PM

Java runs on pretty much anything it wants to...

I went back to the mergeSort alogrithms which is from the Microsystems and I found that mergeSort implemented a superclass that contained a method called "pause", and when I traced the pause back to the superclass and found that there was a Thread.sleep(20); line within the pause() method. I know that merge sort is one of the fastest sorter when it comes to large list but when I tested it on my machine, it just lagged like shit. So, I removed the thread and now..it runs like a beauty...

Just strange to see that Microsystem is even using Thread.sleep() line within a mergeSort...

While we're on the top of sorting alogrithms, I was messing around with Shell Sort and I noticed that as you increase the increments, the sorter is faster and so I just had the increment to match with the length of the array/vector and it runs at the fastest. So..just a tip for those of you who use a shell sort. Have the increment match the length of array or vector.

SiNai · 02-11-2004, 07:24 AM

Thread.sleep() definitely pauses the algorithm for that specified number of milliseconds, we've used it in class for some of the graphical things so they don't zoom right by.. Funny they put that into a sort- especially Microsystems, I hope somebody comes up with an answer to why this is so!

hilbert25 · 02-11-2004, 06:42 PM

Merge sort can be parallelized with multiple threads. I haven't looked at the code, so I don't know if they are even doing that. It could be if they did set it up for multithreading and put the sleep in there so they didn't have to use synchronization? A really bad way of doing it that shouldn't work even.

hilbert25 · 02-11-2004, 06:43 PM

Is it just as accurate without the sleeps? Also, how big a space are you sorting? And what kind of computer is this?

kel · 02-11-2004, 08:03 PM

There is no benefit in parallelizing merge sort on a single processor...
Parallelizing merge sort can't be done properly with threads because of the vagaries of the scheduler.

You need some sort of pram model guarantees.

feelgood · 02-11-2004, 08:42 PM

Quote:

Originally posted by hilbert25
Is it just as accurate without the sleeps? Also, how big a space are you sorting? And what kind of computer is this?

Still accurate without the sleep, the size of the data ranges from 8000 objects to 2 million. Although, I usually get a stack or out of memory errors with 2 million.

02-10-2004, 08:15 PM	#1 (permalink)
feelgood Free Mars! Location: I dunno, there's white people around me saying "eh" all the time	[Java + C] Merge Sort Why is it that when I looked at the merge sort source code provided by several sorting alogrithms websites that contains a "Thread.sleep(something)" which whenever I use it, the merge sorter actually runs longer than insertion, selection or even bubble! So, when I removed the Thread.sleep() part, the merge sort alogrithms just zip by as if it was never there while the thread.sleep is still there, it runs like its a friggin turttle... I know its because of the Thread.sleep() but comon, why is it even there in the first place?? __________________ Looking out the window, that's an act of war. Staring at my shoes, that's an act of war. Committing an act of war? Oh you better believe that's an act of war

02-10-2004, 08:29 PM	#2 (permalink)
n0nsensical Junkie Location: San Francisco	I have no idea...if you're trying to make a fast sort the last thing you want to do is take it off the CPU completely. The only thing I can think of is that the sort could take a long time...and that could be bad on an OS with cooperative multitasking?!?! Does Java even run on any of those? __________________ "Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man's appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded." --Abraham Lincoln

02-10-2004, 08:54 PM	#3 (permalink)
feelgood Free Mars! Location: I dunno, there's white people around me saying "eh" all the time	Java runs on pretty much anything it wants to... I went back to the mergeSort alogrithms which is from the Microsystems and I found that mergeSort implemented a superclass that contained a method called "pause", and when I traced the pause back to the superclass and found that there was a Thread.sleep(20); line within the pause() method. I know that merge sort is one of the fastest sorter when it comes to large list but when I tested it on my machine, it just lagged like shit. So, I removed the thread and now..it runs like a beauty... Just strange to see that Microsystem is even using Thread.sleep() line within a mergeSort... While we're on the top of sorting alogrithms, I was messing around with Shell Sort and I noticed that as you increase the increments, the sorter is faster and so I just had the increment to match with the length of the array/vector and it runs at the fastest. So..just a tip for those of you who use a shell sort. Have the increment match the length of array or vector. __________________ Looking out the window, that's an act of war. Staring at my shoes, that's an act of war. Committing an act of war? Oh you better believe that's an act of war

02-11-2004, 07:24 AM	#4 (permalink)
SiNai Dreams In Digital Location: Iowa	Thread.sleep() definitely pauses the algorithm for that specified number of milliseconds, we've used it in class for some of the graphical things so they don't zoom right by.. Funny they put that into a sort- especially Microsystems, I hope somebody comes up with an answer to why this is so! __________________ I can't seem to remember now What it was like- to live life, before you.. symbiont

02-11-2004, 08:03 PM	#7 (permalink)
kel WARNING: FLAMMABLE Location: Ask Acetylene	There is no benefit in parallelizing merge sort on a single processor... Parallelizing merge sort can't be done properly with threads because of the vagaries of the scheduler. You need some sort of pram model guarantees. __________________ "It better be funny"

02-11-2004, 06:42 PM	#5 (permalink)
hilbert25 Psycho Location: nOvA	Merge sort can be parallelized with multiple threads. I haven't looked at the code, so I don't know if they are even doing that. It could be if they did set it up for multithreading and put the sleep in there so they didn't have to use synchronization? A really bad way of doing it that shouldn't work even.

02-11-2004, 06:43 PM	#6 (permalink)
hilbert25 Psycho Location: nOvA	Is it just as accurate without the sleeps? Also, how big a space are you sorting? And what kind of computer is this?