The Divide-and-Conquer Paradigm as a Basis for Parallel Language Design

Introduction 1.1 A Brief History Since the earliest days of computer programming, algorithms have been known which follow the so-called `divide-and-conquer' method. Many of the best and most widely used computer algorithms are these divide-and-conquer (d-c) algorithms. The binary search algorithm and Hoare's quicksort are two very well known examples. There are many, many others for all types of computing problems, both simple and complicated, both general and specialised. Earlier references to d-c in the programming literature do not attempt to formalise it (e.g. Aho et al. 1974), but simply use the idea informally to help with the explanation of an algorithm. In (Horowitz and Sahni 1978), on the other hand, d-c is described as a control abstraction and a program for it is given in a Pascal-like pseudocode, calling four other procedures to supply the details needed to implement any specific algorithm within the general d-c family. Although Horowitz an