What ideas are there to sort an array of elements into n streams using the insert method?

  • 6
    To be honest, the first idea is to come up with something better than parallel sorting with an insert. - eigenein
  • 1. No need to repeat already asked questions . 2. In WinAPI, I personally did not find functions for sorting arrays. 3. And therefore, formulate the problem correctly. - gecube


2 answers 2

We divide the array into n parts, sort each one in a separate stream by “inserts”, and partial results are merged into one “merge”, which can also be parallelized recursively, if necessary.

  • 2
    In this case, all sorting should be done by merging. Parallel to n parts, then reducing the degree of parallelism, we merge them into the result. Actually, the sorting by inserts here will be present when, in the process of dividing each of the n parts (just before merging), we begin to get quite small (two or three dozen elements) segments. The point here is that merge sorting (non-parallel) has O (N log N) complexity and requires about N / 2 auxiliary memory, and sorting is done with O (N ^ 2) inserts (but without auxiliary memory). Those. from these N / 2 extra memory does not escape. - avp
  • @avp, in this case, the best option is to use for sorting not "insertion" and not "merging", but quick sorting. It will often give the best time, since the initial sequence is static, i.e. does not require modification during sorting. Inserts are convenient when the initial set "comes" gradually, element-wise. And the merger is convenient for the merger, which in this case happens with partial results. But if you start from the complexity of the implementation of such an algorithm, then of course, it will be easier to implement all of the merge. - mega
  • @mega, quicksort is unsustainable, and inserts and merges are robust. It can be fundamentally. Of the stable sorts, in the general case, merge sorting (or its timsort type modifications) is probably the best. For numbers (small key size), the fastest (with a sufficiently large N) will be radixsort (but an additional N of memory is required). You can take some set of sorts and their measurements (for linux) here - avp
  • It is not so important that it is more stable, it is more important how the partially sorted sequences will be processed. Both the inserts and the merge collect a sorted array, and a quick sort simply modifies it, so it doesn't require additional memory (apart from the stack) and stability can be corrected if needed. - mega
  • one
    @mega, you can, of course, use your own concepts, but most likely other people will misunderstand you. - If we use the definition of stability (stability) of the sorting algorithm from Wikipedia (and heaps of other sources), then the sorting by inserts is stable (stable). You can check it experimentally, you can read, for example, at Knut in vol. 3. - avp

@mega , that's the trouble with this comment limit. It is necessary in the answer to the question to answer your comment.

 Ну, хорошо. Опять возвращаемся к тому что было: Ваше понятие устойчивости ни как не влияет на сборку массива, о которой я говорю изначально, т.к. порядок следования элементов в сортировке вставками соблюдается переносом этих элементов в любом случае, а в быстрой сортировке этот порядок соблюдается без переноса, это очень важное качество алгоритма, т.к. объем перемещаемых данных на вставках составляет 100%, исключая первый элемент, в отличие от быстрой сортировки или любой другой сортировки с аналогичным свойством, поэтому она здесь наиболее приемлема.
  1. In sorting by inserts, the element is moved (exchange with the previous one (for sorting ascending)) as long as it is smaller than the previous one. If I am not mistaken on average it will turn out (N ^ 2) / 4 exchanges. In the case of an already ordered array, there will be no exchanges at all. For arrays in which there are many ordered sequences, the number of exchanges will be small.
  2. I did not understand the phrase at all: "... and in the quick sorting this order is observed without transfer"

Do you think that the array element selected as a separator does not move (by exchanges) along the array?

I assure you that it moves just as many times as to the left of it (after the next exchange) it turns out to be larger or to the right smaller. Another question is that in the case of quicksort, these displacements divide the array in half (well, ideally) and further movements ( and comparisons! ) Are carried out only in already separated parts. That is why (it is necessary to take into account the number of comparisons) the complexity of quicksort will be O (N log N).

  • You, by the way, answer the answer, not the question. > I assure you that it moves, exactly as many times as to the left of it (after the next exchange) it turns out to be larger or to the right less. Another question is that in the case of quicksort these displacements divide the array in half (well, ideally) and further movements (and comparisons!) Are carried out only in already separated parts, i.e. in quicksort of movements it turns out less. And what is the argument? I am talking about this. - mega
  • Yes, apparently the dispute about anything. It began with a comparison of stable and unstable algorithms and their applicability. And, in fact, the question of the author of the topic remained unanswered. - IMHO effectively parallel sorting inserts (in existing systems) does not implement. - avp
  • one
    Implement partially in parallel can and can, for example: with blocking the resulting sequence when the stream is accessed to it, for the entire time of searching for a place for each element, i.e. get n blocking the array, and it will be extremely inefficient. This can be done even on fast deadlocks, but the essence will not change - the algorithm will work more slowly than a single-threaded one. - mega
  • Or it will be a very greedy algorithm, if for each position of the element to keep the index of its position in the array, and to block only individual elements, but I do not think that the gain will be worth even the time spent on its development. - mega