In this entry we prove that A_n is simple when n >= 5. We then use this result to prove that there is no generalization of “even” and “odd” permutation to three or more classes – i.e. there is no class of homomorphisms into Z_n, where n > 2.

As promised, the last of a three-part series of entries on sorting in parallel. Here we present a parallel implementation of merge_sort which runs in O(nlog_2(n)) time and achieves fairly good parallelism.

As promised, this is the second entry on parallel sorting. In this entry, we’ll implement merge_sort, and then give two different ways to make it run in parallel. The first one will be a bit simpler than the second one.

We’re going to begin our discussion of parallel algorithms. We’ll do this by giving a parallel version of quick_sort_plus. We finish this entry by extending the “Almost the Master Theorem” to include cases where f(n) = cn^alpha*log_2(n). In our next entry, we’ll introduce merge_sort as well as a couple different parallel versions of it. We’ll also discuss both the theoretical and practical runtimes for these functions.

In this entry, we bring together ideas we’ve been developing about permutations, their sign, cycles, and sorting as well as the run time complexity of the algorithms which compute them.