Algorithms.DivideAndConquer

Documentation

divideAndConquer :: (Foldable f, Monoid s) => (a -> s) -> f a -> s

Divide and conquer strategy. See divideAndConquer1.

divideAndConquer1 :: (Foldable1 f, Semigroup s) => (a -> s) -> f a -> s

Divide and conquer strategy

the running time satifies T(n) = 2T(n/2) + M(n),

where M(n) is the time corresponding to the semigroup operation of s on n elements.

divideAndConquer1With :: Foldable1 f => (s -> s -> s) -> (a -> s) -> f a -> s

Divide and conquer strategy

the running time satifies T(n) = 2T(n/2) + M(n),

where M(n) is the time corresponding to the semigroup operation of s on n elements.

mergeSorted :: Ord a => NonEmpty a -> NonEmpty a -> NonEmpty a

Merges two sorted non-Empty lists in linear time.

mergeSortedLists :: Ord a => [a] -> [a] -> [a]

Merges two sorted lists in linear time.

mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a

Given an ordering and two nonempty sequences ordered according to that ordering, merge them.

running time: \(O(n*T)\), where \(n\) is the length of the list, and \(T\) the time required to compare two elements.

mergeSortedListsBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

Given an ordering and two nonempty sequences ordered according to that ordering, merge them

running time: \(O(n*T)\), where \(n\) is the length of the list, and \(T\) the time required to compare two elements.