Efficiency between two sorting functions

Question

I have created a two functions which sorts integers from lowest value to highest then back to low. Does this type of sort exist? Anyways, I have the following two sorting functions which I have created which produce the same output. I was wondering which is the most efficient of the two? Are there any improvements I can make to either?

1. sortMiddleMax1
   • Create a new reverse sorted list of original
   • Start from index 1 to length of list step by 2
2. sortMiddleMax2
   • Sorts the list in-place
   • Start from last index to 0 step by 2

I tried to make the second more efficient than the first. I did not create a new list in memory and I appended to the end instead of pushing the whole list right. Am I correct in this assumption?

Functions

def sortMiddleMax1(aList=None, verbose=False):
  if aList == None or len(aList) < 2:
    return aList
  else:
    sList = sorted(x, key=None, reverse=True)
    if verbose: print sList
    index = 1
    while index < len(sList):
      tmp = sList[index]
      del sList[index]
      sList.insert(0, tmp)
      index+=2
      if verbose: print sList
    return sList

def sortMiddleMax2(aList=None, verbose=False):
  if aList == None or len(aList) < 2:
    return aList
  else:
    aList.sort()
    if verbose: print aList
    index = len(aList)-1
    while index > 0:
      tmp = aList[index]
      del aList[index]
      aList.append(tmp)
      index-=2
      if verbose: print aList
    return aList

Main

x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8]
print '############# sortMiddleMax1 #############'
x1 = sortMiddleMax1(x, True)
print '############# sortMiddleMax2 #############'
x2 = sortMiddleMax2(x, True)

Output

############# sortMiddleMax1 #############
[9, 8, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[8, 9, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[8, 8, 9, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[6, 8, 8, 9, 8, 7, 5, 5, 4, 3, 3, 2, 1, 1]
[5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 3, 2, 1, 1]
[3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 2, 1, 1]
[2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1, 1]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]
############# sortMiddleMax2 #############
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 8]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 8, 8, 9, 8, 7]
[1, 1, 2, 3, 3, 4, 5, 6, 8, 8, 9, 8, 7, 5]
[1, 1, 2, 3, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4]
[1, 1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

Answer 1

You can use Python's extended slicing. [::2] means take every second element. [::-2] means take every second element from the end and work backwards. Here the first slice starts at 0 for even length list and 1 for odd length lists

>>> x = [1, 4, 6, 8, 3, 5, 7, 1, 5, 8, 3, 9, 2, 8]
>>> x = sorted(x)
>>> x[len(x)%2::2] + x[::-2]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

Answer 2

You can use list slice to get the result without for loop:

x = sorted([1,4,6,8,3,5,7,1,5,8,3,9,2,8])
x2 = x[::2] + x[1::2][::-1]

Answer 3

I suspect your two current versions perform exactly the same. However, they both can be improved by using slices to get at the values in the list, rather than by deleting and inserting values.

Each del and each insert is O(N) and you're doing N/2 of each, so the sort will be O(N^2). Slicing is O(N) as well, but only needs to be done twice. The time taken for the sort O(N log N) will dominate, asymptotically.

def sortMiddle3(aList):
    s = sorted(aList) # sort the provided list

    # now take the even indexed items, followed by the odd indexes in reverse
    if len(s) % 2 == 0: # is the number of items even?
        return s[::2] + s[-1::-2] # if so, the last item has an odd index
    else:
        return s[::2] + s[-2::-2]

Example output:

>>> x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8]
>>> sortMiddle3(x)
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]