CODEWITHSUNDEEP
pythonsortingcomplexity-theory
Coda Highland
Coda Highland

Reputation: 135

What is the algorithmic complexity of this sorting function?

I devised the following sorting algorithm while playing with Legos, based on the idea of always stacking smaller pieces on top of bigger pieces until you come across a piece that doesn't fit on either end of the stack.

My initial impression is that its best-case behavior is O(n) and its worst-case behavior is O(n^2) since it's similar to strand sort, but it's been so long since I've done algorithmic analysis in college that I have no idea what its average behavior is. It looks like it ought to be better than strand sort's average O(n^2), but I don't know how to prove it or what it is.

My implementation uses a linked list to allow insertions on both ends, but a deque would work just as well. The following is Python code for convenience of description, but the C++ version is more efficient.

import math

def merge(x, y):
    output = []
    xp = 0
    yp = 0
    if len(y) == 0 or len(x) == 0 or y[0] > x[-1]:
        return x + y
    elif x[0] > y[-1]:
        return y + x
    while xp < len(x) and yp < len(y):
        if x[xp] < y[yp]:
            output.append(x[xp])
            xp = xp + 1
        else:
            output.append(y[yp])
            yp = yp + 1
    if xp < len(x):
        output = output + x[xp:]
    elif yp < len(y):
        output = output + y[yp:]
    return output

def treeMerge(heads, accum):
    currHead = 0
    while heads[currHead] is not None:
        accum = merge(heads[currHead], accum)
        heads[currHead] = None
        currHead = currHead + 1
    heads[currHead] = accum
    return heads

def legoSort(input):
    heads = [None] * int(math.log(len(input), 2) + 1)
    accum = []
    for i in input:
        # can be <= for speed at the cost of sort stability
        if len(accum) == 0 or i < accum[0]: 
            accum.insert(0,i)
        elif i >= accum[-1]:
            accum.append(i)
        else:
            heads = treeMerge(heads, accum)
            accum = [i]
    for i in heads:
        if i is not None:
            accum = merge(accum, i)
    return accum

Upvotes: 2

Views: 169

Answers (2)

Nuclearman
Nuclearman

Reputation: 5304

Looks like you got something similar to timsort or natural merge.

Upvotes: 1

Pheu Verg
Pheu Verg

Reputation: 230

It is rather boring to research unknown code written in unknown language. You'd rather find it here http://en.wikipedia.org/wiki/Merge_sort at the end of Analysis

Upvotes: 1

Related Questions