M Pivot Sort

Abstract

M(ultiple) Pivot Sort is an in-place comparison based sorting algorithm that performs O(n log n) total data comparisons and moves on lists of records. The algorithm accomplishes this by sorting a small portion of the array and partitioning the array around a number of pivots selected from the small sorted portion. Tests have shown M Pivot Sort performs less total data comparisons and moves than Quick Sort, Heap Sort, and Merge Sort on random lists.


More Information

NEWS: A utility patent application was filed with the United States Patent Office in October of 2005. After this patent is approved, more information, figures, and stats will become available.

  1. Abstract
  2. Outline
  3. Basic Algorithm
  4. Optimizations
  5. Testing

Downloads

  1. Paper in .doc format
  2. Testing suite (C++ console app) code ( offline until patent is filed )

Algorithm's first implementation: 12/1/2004 | Webpage creation: 3/23/2005 | Last Update: 4/10/2005

James Edmondson Home Page

Valid HTML 4.01!