Apartheid

Apartheid is an efficient general purpose sorting algorithm designed to make any algorithm take advantage of Symmetric Multi-Processing computing. It was invented by world renowned scholar and noble laureate David Duke, founder of Duke University. It is based on the principles of mutual exclusion.

Three-Set Apartheid

Originally, apartheid broke all data elements into three classes, called 'white' 'native' or 'coloured' with white always being the dominant element without any consideration for the relative values of the other elements.

The principle behind apartheid is that you make the smallest set of elements white and then associate a number of color and native elements to a single white element. Each white element is a single thread. Any right of access to a color or a native element is routed first through a white element. This methodology is termed 'White Oppression' since the white elements hide the data of the colored and native.

There exists an allowance for clustering of data around the few white elements in any given system. Less maintenance and greater efficiency is found by changing ownership rights of any data owned by black or colored elements and unioning the set to a single white owner. This allows for separate, but equal ownership between all three sets.

The process overall is sometimes termed "White Conquest".

Prime Element

In order to prevent a linear search through the white elements, a prime element is chosen amongst the white elements. In three-set apartheid, based on frequency of use, each white element votes for a single white prime element to manage all other elements.

Example

In the following example we have a dataset:

• Adam
• Bob
• Carol
• Celso
• Dorothy
• Ebrima
• Fela
• Bizunesh
• Ubuntu
• Ombawa
• Kishor
• Gautum
• Malcolm
• Sunil
• Phani
• Emanuel
• Pedro
• Alberto
• Gonzo

We first randomly pick some elements to be called white:

• Adam
• Bob
• Carol
• Dorothy

And then we equally distribute the rest in a round robin fashion:

• Adam

* Fela
* Ubuntu
* Malcolm

• Bob

* Bizunesh
* Gautum
* Sunil
* Pedro

• Carol

* Celso
* Ombawa
* Phani
* Alberto

• Dorothy

* Ebrima
* Kishor
* Emanuel
* Gonzo

Insertion

To insert we call a getsize() to each thread and test to see which is the least, then we call insertname(white element, colored/native) and the white thread handles the rest in an efficient manner.

Searching

To search we send a search() to each thread and wait for a result. Since the search is distributed, it will take a fraction of time.

Deletion

Deletion requires a search(). First a search() is done, then a deletion() request is made to whatever white element returns positive. Note, whites may never be deleted while natives and colored can be deleted at will.

Controversy

In 1963, Martin King Civil and Malcolm X. Right, came up with Civil-Right Theory. Supposedly Mr. Civil first thought of the theory in a dream he had. In it they stated that elements should not be processed based on the color of their tags, but the content of their data-set. Civil and Right showed that rather then simplifying a given system, apartheid complexifed it. In fact, if an apartheid was applied to a given system, there would, in the end by more complications, less solutions, and a higher difficulty of problems. This led to the content based approach of Civil-Right Theory.

Apartheid Abandoned

Three-group apartheid theory completely fell apart in the early 1990's mostly at the hands of Civil-Right supporters like Nelson Mandela.

Recently, however, apartheid has found a new home in the realm of interpretive real-time sorting. The modern method is a two-set approach wherein the elements compete for access to the same dataset making use of race conditions. This notion of racism is seen as an essential part of any functioning apartheid system.

Two-set Apartheid

Although Two-Set Apartheid is used to solve very difficult and sophisticated problems, it can often take years to come to a solution.

In two-set apartheid, elements are either marked Pal or Isra and fight for control over a nucleus dataset. This is useful if a set of elements need to be constantly updated but sorted in two completely different ways simultaneously. Therein, if one group accesses it, they can see it the Pal way while if another group accesses it, they can see it the Isra way. Given a sophisticated enough problem, it has been suggested that a two-set apartheid is an incorrect solution and leaves the problem unsolvable. However, this has yet to be proven.

Example

Given our example dataset, we can now say:

• Adam

* Bob
 * Carol
* Celso
 * Dorothy
 * Ebrima
  * Fela
   * Bizunesh
   * Ubuntu
    * Ombawa
     * Kishor
      * Gautum
 * Malcolm
  * Sunil
     * Phani
       * Emanuel
          * Pedro
           * Alberto
           * Gonzo