A recursive function to sort a list of ints

Question

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]]
        elif l[0]<l[1]:
            return [l[0]]+sort_l(l[1:])
        else:
            return sort_l(l[1:])+[l[0]]

Calling this function on a list [3, 1, 2,4,7,5,6,9,8] should give me:

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

But I get:

print(sort_l([3, 1, 2,4,7,5,6,9,8]))--> [1, 2, 4, 5, 6, 8, 9, 7, 3]

Please help me to fix the problem, actual code would be appreciated. Thanks!

Answer 1

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

def quick_sort(l):
    if len(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]

Answer 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

Answer 3

def maximum(lis):
    if len(lis) == 1:
        return lis[0]
    return maximum(lis[1:]) if lis[0] < lis[1] else maximum(lis[:1] + lis[2:])

def sorter(lis):
    if len(lis) == 1:
        return lis
    x = maximum(lis)
    lis.remove(x)
    return sorter(lis) + [x]

with functional programming:

sor = lambda lis: lis if len(lis) == 1 else [lis.pop(lis.index(reduce(lambda x, y: x if x > y else y, lis)))] + sor(lis)

Answer 4

def quicksort(lst):
    "Quicksort over a list-like sequence"
    if len(lst) == 0:
        return lst
    pivot = lst[0]
    pivots = [x for x in lst if x == 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]

Answer 5

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 = 0

  else:
    bigNumber = array[index]

  return sort(array, (index + 1), bigNumber)

Answer 6

#sort an int list using recursion

global array
array=[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)==0 or temp>=array[-1]:
        array.append(temp)
        return
    a=array[-1]
    array.pop()
    sort2(array,temp)
    array.append(a)
sort1(array)
print(array)

Answer 7

Here i am explaining recursive approach to sort a list. we can follow "Induction Base-condition Hypothesis" recursion approach. so basically we consider our hypothesis here sort_l(nums) function which sorts for given list and Base condition will be found when we have singly number list available which is already sorted. Now in induction step, we insert the temp element (last element of list) in the correct position of given list.
example-

1. sort_l([1,5,0,2]) will make below recursively call
2. sort_l([1]) <-- 5 (here you need to insert 5 in correct position)
3. sort_l([1,5]) <-- 0 (here you need to insert 0 in correct position)
4. sort_l([0,1,5]) <-- 2 (here you need to insert 2 in correct position)
5. sort_l([0,1,5,2]) Finally it will be in sorted list.

====== Below is working code=======

def insert_element(nums, temp):
    if len(nums) == 1:
        if nums[0] > temp:
            nums.insert(0, temp)
        elif nums[0] < temp:
            nums.append(temp)
    else:
        for i in range(len(nums)):
            if nums[i] > temp:
                nums.insert(i, temp)
                break
        if nums[-1] < temp:
            nums.append(temp)


def sort_l(nums): ## hypothesis
    if len(nums)==1: ## base condition
        return nums
    temp = nums[-1]
    nums.pop()
    sort_l(nums)
    insert_element(nums, temp) ## induction
    return nums

Answer 8

This is a complementary answer since both quicksort and complexity are already covered in previous answers. Although, I believe an easy-to-get sort function that covers Python's identity is missing*.

def sort(xs: list) -> list:
    if not xs:
        return xs
    else:
        xs.remove(num := min(xs))
        return [num] + sort(xs)

[*] Python is a (slow) interpreted language, but it has become famous because of its readability and easiness to learn. It doesn't really "reward" its developers for using immutable objects nor it is a language that should be used for computation intensive applications

Answer 9

This is a recursive solution. For an explanation, refer to this video:

arr = [3,1,2,4,7,5,6,9,8]

def insert_fn(arr, temp):  # Hypothesis
    if len(arr) == 0 or arr[-1] <= temp:  # Base - condition
        arr.append(temp)
        return arr
         
    # Induction
    val = arr[-1]
    arr.pop()
    insert_fn(arr, temp)  # Call function on a smaller input.
    arr.append(val)  # Induction step
    return arr

def sort_fn(arr):  # Hypothesis
    if len(arr) == 1:  # Base - condition
        return arr
    
    # Induction
    val = arr[-1]  
    arr.pop()
    sort_fn(arr)  # Call function on a smaller input.
    insert_fn(arr, val) # Induction step
    return arr

print(sort_fn(arr))