English Amiga Board - View Single Post

Samurai_Crow · 12 November 2008, 16:33

If I have to use a comparison sort, I use a natural merge sort. Unlike a quicksort, which degenerates to n^2 passes if you have an already sorted list, it sorts stuff that's in order already using only a single pass.

Here's how it works: You go through the list adding every item to a region list and any time you find something out of order, you start a new region. You may have some regions that are one item long and some that are very long. Then on to the merge phase: You check if there are two or more regions on the first region list. If not then you're already sorted. If so, then take the top two regions and compare the top two entries adding the lower one to another region on a second region list. When one of the regions is empty just copy the rest of the other region to the destination region. Once those two regions are empty, remove them from the source region list and take the next two. If you have one region left at the end, just copy it to the destination list. Switch lists and repeat until you have only one sorted region.

For a Z-buffer, I wouldn't use a comparison sort though. I'd use a base-16 radix sort.

12 November 2008, 16:33	#5
Samurai_Crow Total Chaos forever! Join Date: Aug 2007 Location: Waterville, MN, USA Age: 49 Posts: 2,188	If I have to use a comparison sort, I use a natural merge sort. Unlike a quicksort, which degenerates to n^2 passes if you have an already sorted list, it sorts stuff that's in order already using only a single pass. Here's how it works: You go through the list adding every item to a region list and any time you find something out of order, you start a new region. You may have some regions that are one item long and some that are very long. Then on to the merge phase: You check if there are two or more regions on the first region list. If not then you're already sorted. If so, then take the top two regions and compare the top two entries adding the lower one to another region on a second region list. When one of the regions is empty just copy the rest of the other region to the destination region. Once those two regions are empty, remove them from the source region list and take the next two. If you have one region left at the end, just copy it to the destination list. Switch lists and repeat until you have only one sorted region. For a Z-buffer, I wouldn't use a comparison sort though. I'd use a base-16 radix sort.