SortMergeTopDown

class corsort.SortMergeTopDown(compute_history=False)

Merge sort, top-down version (DFS, i.e. “natural” recursive version).

Examples

>>> merge_sort = SortMergeTopDown(compute_history=True)
>>> my_xs = np.array([4, 1, 7, 6, 0, 8, 2, 3, 5])
>>> merge_sort(my_xs).n_comparisons_
19
>>> merge_sort.history_comparisons_  
[(1, 0), (3, 2), (1, 3), (0, 3), (4, 5), (7, 8), (6, 7), (4, 6), (6, 5), (7, 5),
(8, 5), (4, 1), (1, 6), (6, 0), (7, 0), (0, 8), (8, 3), (3, 5), (2, 5)]
>>> merge_sort.history_distances_
[30, 30, 30, 30, 30, 30, 30, 30, 30, 28, 26, 24, 16, 16, 10, 4, 4, 0, 0, 0]
>>> merge_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.