""" Author: OMKAR PATHAK Created On: 31st July 2017 - Best Case O(n log n) - Average Case O(depends on gap sequence) - Worst Case O(n^2) """ import inspect def sort(_list): """ Shell sort algorithm :param _list: list of integers to sort :return: sorted list """ gap = len(_list) // 2 while gap > 0: for i in range(gap, len(_list)): current_item = _list[i] j = i while j >= gap and _list[j - gap] > current_item: _list[j] = _list[j - gap] j -= gap _list[j] = current_item gap //= 2 return _list # TODO: Are these necessary? def time_complexities(): """ Return information on functions time complexity :return: string """ return "Best Case: O(nlogn), Average Case: O(depends on gap sequence), Worst Case: O(n ^ 2)" def get_code(): """ easily retrieve the source code of the sort function :return: source code """ return inspect.getsource(sort)