The first example will revolve around the mergesort algorithm. This sorting algorithm is based on the divide et impera (divide and conquer) design paradigm. The way it works is very simple. You have a list of numbers you want to sort. The first step is to divide the list into two parts, sort them, and merge the results back into one sorted list. Let me give you a simple example with six numbers. Imagine we have a list, v=[8, 5, 3, 9, 0, 2]. The first step would be to divide the list, v, into two sublists of three numbers: v1=[8, 5, 3] and v2=[9, 0, 2]. Then we sort v1 and v2 by recursively calling mergesort on them. The result would be v1=[3, 5, 8] and v2=[0, 2, 9]. In order to combine v1 and v2 back into a sorted v, we simply consider the first item in both lists, and pick the minimum of those. The first iteration would compare 3 and 0. We pick 0, leaving v2=[2, 9]. Then we rinse and repeat: we compare 3 and 2, we pick 2, so now v2=[9]. Then we compare 3 and 9. This time we pick 3, leaving v1=[5, 8], and so on and so forth. Next we would pick 5 (5 versus 9), then 8 (8 versus 9), and finally 9. This would give us a new, sorted version of v: v=[0, 2, 3, 5, 8, 9].

The reason why I chose this algorithm as an example is twofold. First, it is easy to parallelize. You split the list in two, have two processes work on them, and then collect the results. Second, it is possible to amend the algorithm so that it splits the initial list into any N ≥ 2, and assigns those parts to N processes. Recombination is as simple as dealing with just two parts. This characteristic makes it a good candidate for a concurrent implementation.