3分区合并排序 [英] 3 partition mergesort
问题描述
我的教授指派我的类在三部分分割和合并阵列实施归并。
My professor assigned my class with implementing mergesort in arrays with 3-part partitioning and merging.
这是从教授确切的问题。问题是，我没有发现这样的东西三路归并我只知道3路快速排序，所以我认为他可能是指采取一种阵列，它分为3个部分，然后归并的3份和我一起'米乘第2部分mergesorting在一起，然后用mergesorting第三部分组合的一部分这样做。
That was the exact question from the professor. Problem is I have found no such thing as a 3-way mergesort I only know of a 3-way quicksort so I thought that he probably meant to take an array, split it into 3 parts and then mergesort those 3 parts together and I'm doing this by mergesorting the first 2 parts together and then mergesorting the combined part with the 3rd part.
因为我认为正确，我做了正确的事情（已实施，但我不张贴code，因为它没有任何与我的问题），或者有我的理解错了，有什么像3路归并，我不知道。
Did I think correctly and did I do the right thing (already implemented but I'm not posting the code since it doesn't have anything to do with my question) or have I understood wrong and there is something like a 3-way mergesort that I am not aware of.
教授往往给我们说有东西，我们还没有学会做没有，这就是为什么我很怀疑这一点，我在谷歌的长相，我可以等。
The professor tends to give us assignments that have to do with stuff that we have not learned yet that's why I'm so sceptical about this and I looked as much as I could in Google etc.
推荐答案
一旦你mergesorted三个子阵列，可以一气呵成它们合并起来：比较三者的第一要素，并把最小的到组合阵列，然后采取从数组你拿了最小的下一个元素，并再次做compariosn直到所有子数组元素占了。
Once you mergesorted the three sub arrays, you can merge them together in one go: compare the first elements of all three and place the smallest into the combined array, then take the next element from the array you took the smallest from and do the compariosn again until all subarray elements are accounted for.
请确保你喊得那里只有两个数组中的元素的情况下（所以你不能将它划分成三个非空部分）。此外，在上段，一个阵列会合并时，在别人面前空的，所以你需要考虑这一点。
Make sure you hande the case where there are only two elements in the array (so you cannot partition it into three non-empty parts). Also, in the above paragraph, one array will be empty before the others when merging, so you need to account for that too.
这篇关于3分区合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
