This page contains a collection of parallel algorithm on sequences and
strings. It includes a brief description of each algorithm along with
the NESL code. These algorithms have been
developed by the Scandal project.

The algorithm we use is a standard tree-based algorithm that requires
a total of O(n) work and O(log n) depth. The
code shown here works if the length of the array is a power of 2.

This is a simple O(n^2) work and constant depth algorithm
that sorts by counting how many keys are less than every key. To
account for duplicate keys we need to tag each value with its index
and then make pairwise comparisons.

Here is Batcher's odd-even merge. It has total work O(n
log n) and depth O(log n). It is therefore
not work efficient.
As written it only works if both lists are equal lengths and are powers of 2.

The parallel quickselect algorithm is based on the sequential version.
Like quicksort it picks a pivot and then finds the keys less and greater
than the pivot. Unlike quicksort, it only has to recurse on one of these
two sets rather than both since it can determine in which of the sets the
kth element belongs. Because of this is has expected work O(n)
instead of O(n log n) for quicksort. Like quicksort, its
depth is O(log n), expected.

This is a select algorithm that has O(n) work
and constant depth with high probability. The idea is to take a sample
of the data of size sqrt(n) and then do an n^2 algorithm to find a
range in that sample (kmin,kmax) in which the kth element is likely
to appear. This technique quickly restricts the range in which
the algorithm has to consider.

This algorithm for comparing two string a and b returns -1 if a < b,
returns 0 if a = b and returns 1 if a > b. It uses a reduce (which is
implemented on a tree) to combine the values from each character. The
work of the algorith is O(#s1 + #s2) and the depth is
O(log(min(#s1,#s2))).

This is an interesting algorithm since one might think that matching
parentheses seems very sequential. For each location the algorithm
returns the index of the matching parenthesis. The algorithm is based
on a scan and an interger sort (rank). The scan returns the depth of
each parenthesis and the sort groups them into groups of equal depth.
At this point we can simply switch the indices of neighbors.
Assuming a work-efficient radix sort, this algorithm does O(n)
work and has the depth is bounded by the sort.