A Recursive Function To Sort A List Of Ints

I want to define a recursive function can sort any list of ints: def sort_l(l): if l==[]: return [] else: if len(l)==1: return [l[-1]] e

Solution 1:

The quick sort is recursive and easy to implement in Python:

defquick_sort(l):
    iflen(l) <= 1:
        return l
    else:
        return quick_sort([e for e in l[1:] if e <= l[0]]) + [l[0]] +\
            quick_sort([e for e in l[1:] if e > l[0]])

will give:

>>> quick_sort([3, 1, 2, 4, 7, 5, 6, 9, 8])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Solution 2:

For this you would want to use merge sort. Essentially in a merge sort you recursively split the list in half until you have single elements and than build it back up in the correct order. merge sort on has a complexity of O(n log(n)) and is an extremely stable sorting method.

Here are some good in depth explanations and visuals for merge sorting:

• https://www.youtube.com/watch?v=vxENKlcs2Tw
• http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Merge_sort.html

Solution 3:

def quicksort(lst):
    "Quicksort over a list-like sequence"iflen(lst) == 0:
        returnlstpivot= lst[0]
    pivots = [x for x in lst ifx== pivot]
    small = quicksort([x for x in lst if x < pivot])
    large = quicksort([x for x in lst if x > pivot])
    return small + pivots + large

Above is a more readable recursive implementation of Quick Sort Algorithm. Above piece of code is from book Functional programing in python by O'REILLY. Above function will produce.

list=[9,8,7,6,5,4]
quicksort(list)
>>[4,5,6,7,8,9]

Solution 4:

def sort(array, index = 0, bigNumber = 0):
  if len(array) == index:
    return array

  elif bigNumber > array[index]:
    array[index - 1] = array[index]
    array[index] = bigNumber
    bigNumber = array[0]
    index = 0else:
    bigNumber = array[index]

  returnsort(array, (index + 1), bigNumber)

Solution 5:

#sort an int list using recursion

globalarrayarray=[5,3,8,4,2,6,1]
def sort1(array:[])->[]:
    if len(array)==1:
        return 
    temp=array[-1]
    array.pop()
    sort1(array)
    sort2(array,temp)
def sort2(array:[],temp):
    if len(array)==0or temp>=array[-1]:
        array.append(temp)
        return
    a=array[-1]
    array.pop()
    sort2(array,temp)
    array.append(a)
sort1(array)
print(array)