What is the real name of median sort and/or where can I find more material on it_问答_开发者

I'm reading the book Algorithms in a Nutshell published by O'Reilly Media and I was reading the section on sorting algorithms and found one called Median Sort. Since I had never heard of it before and my textbook from CS3 (which covered algorithms) did not have it listed, I开发者_运维问答 googled it and tried looking it up on Wikipedia and found nothing. I would greatly appreciate it if someone could provide the name I could easily look the algorithm up under or point me to other resources about it. Thank you.

Also, from what I can tell about the algorithm, it's essentially Quicksort except it always uses the median value as the pivot. By median value I mean it seems to scan the array of items and pick the middle value as the pivot, not pick the middle item in the array as the pivot. Also, the book mentions a Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) in relation to the "Median" sort.

Most versions of quicksort pick (for example) the median of three elements (typically the first, middle and last), giving what's normally called a median of 3 Quicksort. Just starting with the middle element as the pivot doesn't usually qualify for any name other than just Quicksort.

Edit (much later, after seeing the edit in the question): it appears that what you're talking about is using the "median of medians" algorithm to choose the pivot element for a QuickSort. The median of medians algorithm is better known for being used independently as an alternative to (or refinement of, depending on your viewpoint) Hoare's Select algorithm. This is known to find the median (or other rank, but in this case we only care about median) in linear time.

The bottom line is that the sort is really still a Quicksort. Hoare's description of choosing the pivot element neither requires nor prohibits a media of medians selection:

The first step of the partition process is to choose a particular key value which is known to be within the range of the keys of the items in the segment which is to be sorted. A simple method of ensuring this is to choose the actual key value of one of the items in the segment. The chosen key value will be called the bound.

Of course, nearly everybody now calls it the "pivot" instead of the "bound", but this is mostly irrelevant. The method used to choose the pivot/bound is left open.

As I don't own the aforementioned book, I'll take a wild guess and say that Blum-Floyd-Pratt-Rivest-Tarjan algorithm (also see the paper if you want to know more) is probably used for pivot selection. I also recommend you to read the Partition-based general selection algorithm section from the same Wikipedia article as I think it is exactly what you are looking for.

Yes you are right it is similar to quicksort but it is better than Quicksort in the way that it avoids those cases where your arrays are divided very disprorportionately(not in equal halves). Because in quicksort we cannot be sure that each time our array will be divided into two equal halves or nearly equal halves.In median sort we assure this by paying price for finding median but that could be worthy to make quick sort similar to merge sort and benefits of having sorting in place.

I don't own the book but I will take a guess. The algorithm the book is referring to is the Floyd-Rivest's SELECT algorithm. Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) refers to this paper where they discuss their earlier PICK (now known as Median of medians) selection algorithm:

M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan, “Time Bounds for Selection,” Journ. Comp. and. Sys. Sci., vol. 7, iss. 4, pp. 448-461, 1973.

This paper sets up the early understanding of the selection problem in computer science.