SortMultizip

class corsort.SortMultizip(compute_history=False)

Multizip sort.

Like bottom-up (BFS) mergesort, we compare pairs first, then quadruples, etc. But at each steps, all merges are done in “multizip” style, i.e. one comparison for the first merge, then one for the second merge, etc.

Examples

>>> multizip_sort = SortMultizip(compute_history=True)
>>> my_xs = np.array([4, 1, 7, 6, 0, 8, 2, 3, 5])
>>> multizip_sort(my_xs).n_comparisons_
19
>>> multizip_sort.history_comparisons_  
[(7, 8), (1, 0), (3, 2), (4, 5), (6, 7), (1, 3), (4, 6), (0, 3), (6, 5),
(7, 5), (8, 5), (4, 1), (1, 6), (6, 0), (7, 0), (0, 8), (8, 3), (3, 5), (2, 5)]
>>> multizip_sort.history_distances_
[30, 30, 30, 30, 30, 30, 30, 30, 30, 28, 26, 24, 16, 16, 10, 4, 4, 0, 0, 0]
>>> multizip_sort.sorted_list_
array([0, 1, 2, 3, 4, 5, 6, 7, 8])

distance_to_sorted_array()

Distance to sorted array.

Returns:

Distance between the current estimation and the sorted array.

Return type:

int

property history_comparisons_values_

History of the pairwise comparisons, in terms of compared values. Tuple (x, y) means that items of values x and y were compared, and that x < y.

Type:

list of tuple

test_i_lt_j(i, j)

Test whether perm[i] < perm[j].

Parameters:

• i (int) – First index.

• j (int) – Second index.

Returns:

True if item of index i is lower than item of index j.

Return type:

bool

Notes

The history of distance is computed just before the comparison. Hence it should be computed a last time at the end of the algorithm.