Library sort: Difference between revisions

Revision as of 23:59, 22 July 2013

Revision as of 06:37, 15 August 2013

Line 13:

The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>http://arxiv.org/abs/cs/0407003</ref> and published 2006.<ref name="definition">

{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391 | year=2006 | author=Bender, M. A., Farach-Colton, M., and Mosteiro M. | title=Insertion Sort is O(n log n) | doi = 10.1007/s00224-005-1237-z }}</ref>

Like the insertion sort it is based on, library sort is a [[stable sort|stable]] [[comparison sort]] and can be run as an [[online algorithm]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n²). The mechanism used for this improvement is very similar to that of a [[skip list]]. There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the library sort efficiency compares to other sorting methods in reality.

Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would be implementation dependent. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" />, but with no further recommendations on how to choose ε. One weakness of [[insertion sort]] is that it may require a high number of swap operations and be costly if memory write is expensive. Library sort may improve that somewhat in the insertion step, as fewer elements need to move to make room, but is also adding an extra cost in the rebalancing step.

==Implementation==

===Algorithm ===

Let us say we have an array of n elements. We choose the gap we intend to

Line 28 ⟶ 29:

following elements till we hit an empty space. Once the round is over, we

re-balance the final array by inserting spaces between each element.

Following are three important steps of the algorithm:

1. Binary Search:

Line 38 ⟶ 37:

left or right side of the array if you hit a empty space in the middle

element.

2. Insertion:

Inserting the element in the position found and swapping the following

elements by 1 position till an empty space is hit.

3. Re-Balancing:

Line 205 ⟶ 202:

}

</source>

===Python Implementation===

<source lang="python">

Line 226 ⟶ 224:

if array[m] == element: return m + 1

elif array[m] > element: return binary_search(array, element, start, m-1)

else: return binary_search(array, element, m+1, end)

def insert(array, element, index):

Line 241 ⟶ 238:

if index > last_insert_index:

last_insert_index = index

def balance(array, num_spaces, total_inserted):