def cocktail_shaker_sort(arr):
def swap(i, j):<EOL><INDENT>arr[i], arr[j] = arr[j], arr[i]<EOL><DEDENT>n = len(arr)<EOL>swapped = True<EOL>while swapped:<EOL><INDENT>swapped = False<EOL>for i in range(<NUM_LIT:1>, n):<EOL><INDENT>if arr[i - <NUM_LIT:1>] > arr[i]:<EOL><INDENT>swap(i - <NUM_LIT:1>, i)<EOL>swapped = True<EOL><DEDENT><DEDENT>if swapped == False:<EOL><INDENT>return arr<EOL><DEDENT>swapped = False<EOL>for i in range(n-<NUM_LIT:1>,<NUM_LIT:0>,-<NUM_LIT:1>):<EOL><INDENT>if arr[i - <NUM_LIT:1>] > arr[i]:<EOL><INDENT>swap(i - <NUM_LIT:1>, i)<EOL>swapped = True<EOL><DEDENT><DEDENT><DEDENT>return arr<EOL>
Cocktail_shaker_sort
Sorting a given array
mutation of bubble sort

reference: https://en.wikipedia.org/wiki/Cocktail_shaker_sort

Worst-case performance: O(N^2)