Problem Statement

The   cocktail sort   is an improvement on the   Bubble Sort.

A cocktail sort is also known as:

The improvement is basically that values "bubble"   (migrate)   both directions through the array,   because on each iteration the cocktail sort   bubble sorts   once forwards and once backwards. After   ii   passes,   the first   ii   and the last   ii   elements in the array are in their correct positions,   and don't have to be checked (again). By shortening the part of the array that is sorted each time,   the number of comparisons can be halved.

Pseudocode for the   2nd   algorithm   (from Wikipedia)   with an added comment and changed indentations: %   indicates a comment,   and   deal   indicates a   swap.

Implement a   cocktail sort   and optionally show the sorted output here on this page. See the   discussion   page for some timing comparisons.

Let's start with the solution:

cocktailShiftSort: function [items][
    a: new items
    beginIdx: 0
    endIdx: (size a)-2

    while [beginIdx =< endIdx][
        newBeginIdx: endIdx
        newEndIdx: beginIdx

        loop beginIdx..endIdx 'i [
            if a\[i] > a\[i+1] [
                tmp: a\[i]
                a\[i]: a\[i+1]
                a\[i+1]: tmp
                newEndIdx: i
            ]
        ]

        endIdx: newEndIdx - 1

        loop endIdx..beginIdx 'i [
            if a\[i] > a\[i+1] [
                tmp: a\[i]
                a\[i]: a\[i+1]
                a\[i+1]: tmp
                newBeginIdx: i
            ]
        ]

        beginIdx: newBeginIdx - 1
    ]
    return a
]

print cocktailShiftSort [3 1 2 8 5 7 9 4 6]