def mergeSort(x):
    if len(x) == 0 or len(x) == 1:
        return x
    else:
        middle = len(x)//2
        a = mergeSort(x[:middle])
        b = mergeSort(x[middle:])
        return merge(a,b)

def merge(a,b):
    c = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',mergeSort(List))

def merge(a,b):
    c = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

# Code for merge sort

def mergeSort(x):
    if len(x) == 0 or len(x) == 1:
        return x
    else:
        middle = len(x)//2
        a = mergeSort(x[:middle])
        b = mergeSort(x[middle:])
        return merge(a,b)

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',mergeSort(List))

def selectionSort(List):
    for i in range(len(List) - 1):
        minimum = i
        for j in range( i + 1, len(List)):
            if(List[j] < List[minimum]):
                minimum = j
        if(minimum != i):
            List[i], List[minimum] = List[minimum], List[i]
    return List

Best O(n^2); Average O(n^2); Worst O(n^2)

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List:',selectionSort(List))

def selectionSort_Ascending(List):
    for i in range(len(List) - 1):
        minimum = i
        for j in range( i + 1, len(List)):
            if(List[j] < List[minimum]):
                minimum = j
        if(minimum != i):
            List[i], List[minimum] = List[minimum], List[i]
    return List

def selectionSort_Descending(List):
    for i in range(len(List) - 1):
        minimum = i
        for j in range(len(List)-1,i,-1):
            if(List[j] > List[minimum]):
                minimum = j
        if(minimum != i):
            List[i], List[minimum] = List[minimum], List[i]
    return List

if __name__ == '__main__':
    List1 = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List Ascending:',selectionSort_Ascending(List1))
    print('Sorted List Descending:',selectionSort_Descending(List1))

Bubble Sort: (array)
  n := length(array)
  repeat
  swapped = false
  for i := 1 to n - 1 inclusive do

      /* if this pair is out of order */
      if array[i - 1] > array[i] then

        /* swap them and remember something changed */
        swap(array, i - 1, i)
        swapped := true

      end if
    end for
  until not swapped

  for j = 0 to loop-1 do:

     /* compare the adjacent elements */   
     if list[j] > list[j+1] then
        /* swap them */
        swap( list[j], list[j+1] )         
        swapped = true
     end if

  end for

  /*if no number was swapped that means 
  array is sorted now, break the loop.*/

  if(not swapped) then
     break
  end if

function swap(array, idx1, idx2) {
  let temp = array[idx1];
  array[idx1] = array[idx2];
  array[idx2] = temp;
}

function bubbleSort(array) {
  let swapped = true;

  while (swapped) {
    swapped = false;

    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        swap(array, i, i + 1);

        swapped = true;
      }
    }
  }

  return array;
}

let array1 = [2, -1, 4, 3, 7, 3];
bubbleSort(array1);
console.log(" bubbleSort(array): ", bubbleSort(array1));
module.exports = { bubbleSort: bubbleSort, swap: swap };

procedure selection sort(list)
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i

      /* check the element to be minimum */

      for j = i+1 to n
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
end procedure

function swap(arr, index1, index2) {
  let temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

function selectionSort(list) {
  let length = list.length;
  for (let i = 0; i < length - 1; i++) {
    let minPos = i;

    for (let j = i + 1; j < length; j++) {
      if (list[j] < list[minPos]) {
        minPos = j;
      }
    }

    if (minPos !== i) {
      swap(list, minPos, i);
    }
  }
}
module.exports = {
  selectionSort,
  swap,
};

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert

   for i = 1 to length(A) inclusive do:

      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i

      /*locate hole position for the element to be inserted */

      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while

      /* insert the number at hole position */
      A[holePosition] = valueToInsert

   end for

end procedure

function insertionSort(list) {
  for (let i = 1; i < list.length; i++) {
    let val = list[i];
    let pos = i;
    // console.trace("1");
    while (pos > 0 && list[pos - 1] > val) {
      // console.trace("2");
      list[pos] = list[pos - 1];
      pos -= 1;
    }
    list[pos] = val;
  }
}
let array = [2, -1, 4, 3, 7, 3];
insertionSort(array);
module.exports = {
  insertionSort,
};

procedure mergesort( a as array )
   if ( n == 1 ) return a

   /* Split the array into two */
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( a as array, b as array )
   var result as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of result
         remove b[0] from b
      else
         add a[0] to the end of result
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of result
      remove a[0] from a
   end while

   while ( b has elements )
      add b[0] to the end of result
      remove b[0] from b
   end while

   return result
end procedure

// Implement Merge Sort

function merge(array1, array2) {
  let merged = [];

  while (array1.length || array2.length) {
    let el1 = array1.length ? array1[0] : Infinity;
    let el2 = array2.length ? array2[0] : Infinity;

    el1 < el2 ? merged.push(array1.shift()) : merged.push(array2.shift());
  }

  return merged;
}

merge([1, 5, 10, 15], [0, 2, 3, 7, 10]);

function mergeSort(array) {
  if (array.length <= 1) return array;

  let midIdx = Math.floor(array.length / 2);
  let left = array.slice(0, midIdx);
  let right = array.slice(midIdx);

  let sortedLeft = mergeSort(left);
  let sortedRight = mergeSort(right);

  return merge(sortedLeft, sortedRight);
}

module.exports = {
  merge,
  mergeSort,
};

procedure quick sort (array)
  if the length of the array is 0 or 1, return the array

  set the pivot to the first element of the array
  remove the first element of the array

  put all values less than the pivot value into an array called left
  put all values greater than the pivot value into an array called right

  call quick sort on left and assign the return value to leftSorted
  call quick sort on right and assign the return value to rightSorted

  return the concatenation of leftSorted, the pivot value, and rightSorted
end procedure quick sort

// Implement Quick Sort

function quickSort(array) {
  if (array.length <= 1) return array;

  let pivot = array.shift();

  let left = array.filter((el) => el < pivot);
  let right = array.filter((el) => el >= pivot);

  let sortedLeft = quickSort(left);
  let sortedRight = quickSort(right);

  return [...sortedLeft, pivot, ...sortedRight];
}

module.exports = {
  quickSort,
};

/*
bryan@LAPTOP-F699FFV1:/mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master/problems$ npm test

> bubble_sort_project_solution@1.0.0 test /mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master
> mocha

 bubbleSort(array):  [ -1, 2, 3, 3, 4, 7 ]


  bubbleSort()
    ✓ should sort the elements of the array in increasing order, in-place

  swap()
    ✓ should swap the elements at the given indices, mutating the original array

  selectionSort()
    ✓ should sort the elements of the array in increasing order, in-place

  insertionSort()
    ✓ should sort the elements of the array in increasing order, in-place

  merge()
    ✓ should return a single array containing elements of the original sorted arrays, in order

  mergeSort()
    when the input array contains 0 or 1 elements
      ✓ should return the array
    when the input array contains more than 1 element
      ✓ should return an array containing the elements in increasing order

  quickSort()
    when the input array contains 0 or 1 elements
      1) should return the array
    when the input array contains more than 1 element
      2) should return an array containing the elements in increasing order


  7 passing (210ms)
  2 failing

  1) quickSort()
       when the input array contains 0 or 1 elements
         should return the array:
     AssertionError: expected undefined to deeply equal []
      at Context.<anonymous> (test/05-quick-sort-spec.js:9:32)
      at processImmediate (internal/timers.js:456:21)

  2) quickSort()
       when the input array contains more than 1 element
         should return an array containing the elements in increasing order:
     AssertionError: expected undefined to deeply equal [ -1, 2, 3, 3, 4, 7 ]
      at Context.<anonymous> (test/05-quick-sort-spec.js:16:49)
      at processImmediate (internal/timers.js:456:21)



npm ERR! Test failed.  See above for more details.
bryan@LAPTOP-F699FFV1:/mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master/problems$ npm test

> bubble_sort_project_solution@1.0.0 test /mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master
> mocha

 bubbleSort(array):  [ -1, 2, 3, 3, 4, 7 ]


  bubbleSort()
    ✓ should sort the elements of the array in increasing order, in-place

  swap()
    ✓ should swap the elements at the given indices, mutating the original array

  selectionSort()
    ✓ should sort the elements of the array in increasing order, in-place

  insertionSort()
    ✓ should sort the elements of the array in increasing order, in-place

  merge()
    ✓ should return a single array containing elements of the original sorted arrays, in order

  mergeSort()
    when the input array contains 0 or 1 elements
      ✓ should return the array
    when the input array contains more than 1 element
      ✓ should return an array containing the elements in increasing order

  quickSort()
    when the input array contains 0 or 1 elements
      ✓ should return the array
    when the input array contains more than 1 element
      ✓ should return an array containing the elements in increasing order


  9 passing (149ms)

*/

procedure binary search (list, target)
  parameter list: a list of sorted value
  parameter target: the value to search for

  if the list has zero length, then return false

  determine the slice point:
    if the list has an even number of elements,
      the slice point is the number of elements
      divided by two
    if the list has an odd number of elements,
      the slice point is the number of elements
      minus one divided by two

  create an list of the elements from 0 to the
    slice point, not including the slice point,
    which is known as the "left half"
  create an list of the elements from the
    slice point to the end of the list which is
    known as the "right half"

  if the target is less than the value in the
    original array at the slice point, then
    return the binary search of the "left half"
    and the target
  if the target is greater than the value in the
    original array at the slice point, then
    return the binary search of the "right half"
    and the target
  if neither of those is true, return true
end procedure binary search

procedure binary search index(list, target, low, high)
  parameter list: a list of sorted value
  parameter target: the value to search for
  parameter low: the lower index for the search
  parameter high: the upper index for the search

  if low is equal to high, then return -1 to indicate
    that the value was not found

  determine the slice point:
    if the list has an even number of elements,
      the slice point is the number of elements
      divided by two
    if the list has an odd number of elements,
      the slice point is the number of elements
      minus one divided by two

  if the target is less than the value in the
    original array at the slice point, then
    return the binary search of the array,
    the target, low, and the slice point
  if the target is greater than the value in the
    original array at the slice point, then return
    the binary search of the array, the target,
    the slice point plus one, and high
  if neither of those is true, return true
end procedure binary search index

def insertionSort(List):
    for i in range(1, len(List)):
        currentNumber = List[i]
        for j in range(i - 1, -1, -1):
            if List[j] > currentNumber :
                List[j], List[j + 1] = List[j + 1], List[j]
            else:
                List[j + 1] = currentNumber
                break

    return List

Best O(n); Average O(n^2); Worst O(n^2)

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',insertionSort(List))

def insertionSort(List):
    for i in range(1, len(List)):
        currentNumber = List[i]
        for j in range(i - 1, -1, -1):
            if List[j] > currentNumber :
                List[j], List[j + 1] = List[j + 1], List[j]
            else:
                List[j + 1] = currentNumber
                break

    return List

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',insertionSort(List))

def quickSort(myList, start, end):
    if start < end:
        pivot = partition(myList, start, end)
        quickSort(myList, start, pivot-1)
        quickSort(myList, pivot+1, end)
    return myList

def partition(myList, start, end):
    pivot = myList[start]
    left = start+1
    right = end
    done = False
    while not done:
        while left <= right and myList[left] <= pivot:
            left = left + 1
        while myList[right] >= pivot and right >=left:
            right = right -1
        if right < left:
            done= True
        else:
            temp=myList[left]
            myList[left]=myList[right]
            myList[right]=temp
    temp=myList[start]
    myList[start]=myList[right]
    myList[right]=temp
    return right

def quicksortBetter(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksortBetter(left) + middle + quicksortBetter(right)

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    start = time.time()
    print('Sorted List:',quickSort(List, 0, len(List) - 1))
    stop = time.time()
    print('Time Required:', (stop - start))
    start = time.time()
    print('Sorted List:', quicksortBetter(List))
    stop = time.time()
    print('Time Required:', (stop - start))

import time

def quickSort(myList, start, end):
    if start < end:
        pivot = partition(myList, start, end)
        quickSort(myList, start, pivot-1)
        quickSort(myList, pivot+1, end)
    return myList

def partition(myList, start, end):
    pivot = myList[start]
    left = start+1
    right = end
    done = False
    while not done:
        while left <= right and myList[left] <= pivot:
            left = left + 1
        while myList[right] >= pivot and right >=left:
            right = right -1
        if right < left:
            done= True
        else:
            temp=myList[left]
            myList[left]=myList[right]
            myList[right]=temp
    temp=myList[start]
    myList[start]=myList[right]
    myList[right]=temp
    return right

# A more efficient solution
def quicksortBetter(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksortBetter(left) + middle + quicksortBetter(right)

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    start = time.time()
    print('Sorted List:',quickSort(List, 0, len(List) - 1))
    stop = time.time()
    print('Time Required:', (stop - start))
    start = time.time()
    print('Sorted List:', quicksortBetter(List))
    stop = time.time()
    print('Time Required:', (stop - start))

import random

# TO-DO: complete the helper function below to merge 2 sorted arrays
def merge( arrA, arrB ):
    elements = len( arrA ) + len( arrB )
    merged_arr = [0] * elements

    # Iterate through marged_arr to insert smallest item in arrA and arrB until merged_arr is full
    for i in range(0, len(merged_arr)):
        # If arrA is empty, use arrB to fill
        if len(arrA) == 0:
            merged_arr[i] = min(arrB)
            arrB.remove(min(arrB))
        
        # If arrB is empty, use arrA to fill
        elif len(arrB) == 0:
            merged_arr[i] = min(arrA)
            arrA.remove(min(arrA))

        # If the smallest item in arrA is smaller than the smallest item in arrB, insert arrA's smallest item and then remove from arrA
        elif min(arrA) < min(arrB):
            merged_arr[i] = min(arrA)
            arrA.remove(min(arrA))

        # If the smallest item in arrB is smaller than the smallest item in arrA, insert arrB's smallest item and then remove from arrB
        elif min(arrA) >= min(arrB):
            merged_arr[i] = min(arrB)
            arrB.remove(min(arrB))
    
    return merged_arr

# TO-DO: implement the Merge Sort function below USING RECURSION
def merge_sort( arr ):
    if len(arr) == 0 or len(arr) == 1:
        return arr
    
    mid_point = round(len(arr)/2)
    arrA = merge_sort(arr[:mid_point])
    arrB = merge_sort(arr[mid_point:])

    return merge(arrA,arrB)

# STRETCH: implement an in-place merge sort algorithm
def merge_in_place(arr, start, mid, end):
    # Updating the pointers
    # Getting past the halfway 
    # Assign a variable to track the index of the other starting point 
    # Decrement

    return arr

def merge_sort_in_place(arr, l, r): 
    # TO-DO

    return arr


# STRETCH: implement the Timsort function below
# hint: check out https://github.com/python/cpython/blob/master/Objects/listsort.txt

def insertion_sort(arr):
    for i in range(1, len(arr)):
        # Starts looping from first unsorted element
        unsorted = arr[i]
        # Starts comparing against last sorted element
        last_sorted_index = i-1

        # While unsorted is less than the last sorted...
        while last_sorted_index >= 0 and unsorted < arr[last_sorted_index]:
            # Shifts last sorted to the right by one
            arr[last_sorted_index + 1] = arr[last_sorted_index]
            # Decrements down the last sorted index, until no longer larger than or hits zero
            last_sorted_index -= 1

        # Places unsorted element into correct spot
        arr[last_sorted_index + 1] = unsorted
    return arr


def timsort( arr ):
    # Divide arr into runs of 32 (or as chosen)
    # If arr size is smaller than run, it will just use insertion sort
    minirun = 32
    for i in range(0, len(arr), minirun):
        counter = 0
        range_start = minirun * counter
        range_end = minirun * (counter+1)
        print(range_start, range_end)
        print(f"i is: {i}")
        print(insertion_sort(arr[range_start:range_end]))
        counter += 1

    # Sort runs using insertion sort
    # Merge arrays using merge sort

    
    # return insertion_sort(arr)

test_sort = random.sample(range(100), 64)
print(timsort(test_sort))

def partition(A, lo, hi):
    pivot = A[lo + (hi - lo) // 2]
    i = lo - 1
    j = hi + 1

    while True:

        i += 1
        while A[i] < pivot:
            i += 1

        j -= 1
        while A[j] > pivot:
            j -= 1

        if i >= j:
            return j
        A[i], A[j] = A[j], A[i]


def quicksort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)
    return A


if __name__ == "__main__":
    arr = [8, 3, 5, 1, 7, 2]
    quicksort(arr, 0, len(arr) - 1)
    #  >>> [1, 2, 3, 5, 7, 8]

Consider an array a=[5,4,3,2,1]
Iteration 1:-
         |5|4|3|2|1|
          |___________5>4 therefore we swap both of them.
         |4|5|3|2|1|
            |_________5>3 therefore we swap both.
         |4|3|5|2|1|
              |_______5>2 therefore we swap.
         |4|3|2|5|1|
                |_____5>1 therefore we swap.
         |4|3|2|1|5| Now 5 is placed at its original position

Iteration 2:-
         |4|3|2|1|5|
          |__________4>3 therefore we swap both.
         |3|4|2|1|5|
            |________4>2 therefore we swap both.
         |3|2|4|1|5|
              |______4>1 therefore we swap both.
         |3|2|1|4|5|
                 |__ 4 is placed at its original position.

Iteration 3:-
         |3|2|1|4|5|
          |_________3>2 we swap.
         |2|3|1|4|5|
            |_______3>1 we swap.
         |2|1|3|4|5|- 3 is placed at original position.

Iteration 4:-
          |2|1|3|4|5|
           |_________2>1 we swap.
          |1|2|3|4|5| the array is sorted.

#Link to problem:- 
#Bubble sort is a sorting algorithm. Sorting algorithms are used to arrange the array in particular order.In,Bubble sort larger elements are pushed at the end of array in each iteration.It works by repeatedly swapping the adjacent elements if they are in wrong order.

def bubbleSort(a): 
    n = len(a) 
    # Traverse through all array elements 

    for i in range(n-1): 
        # Last i elements are already in place 
        for j in range(0, n-i-1): 

            # traverse the array from 0 to n-i-1 
            # Swap if the element found is greater 
            # than the next element 
            if arr[j] > arr[j + 1] : 
                arr[j], arr[j + 1] = arr[j + 1], arr[j] 

arr = []
n=int(input("Enter size of array: "))
for i in range(n):
    e=int(input())
    arr.append(e)
bubbleSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
     print(arr[i])
     
#Time complexity - O(n^2)
#Space complexity - O(1)

# Insertion Sort

## Aim

The main aim of the script is to sort numbers in list using insertion sort.

## Purpose

The main purpose is to sort list of any numbers in O(n) or O(n^2) time complexity.

## Short description of package/script

Takes in an array. <br>
Sorts the array and prints sorted array along with the number of swaps and comparisions made.
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

## Detailed explanation of script, if needed

To sort an array of size n in ascending order: <br>
1: Iterate from a[1] to a[n] over the array. <br>
2: Compare the current element (val) to its predecessor. <br>
3: If the val is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element. <br>

## Setup instructions

Download code and run it in any python editor. Latest version is always better.

## Compilation Steps

1.Edit array a and enter your array/list you want to sort. 2. Run the code

## Sample Test Cases

### Test case 1:

input:<br>
a = [34,5,77,33] <br>

output :<br>

5, 33, 34, 77 along with <br>
no. of swaps = 3 <br>
no. of comparisons=5<br>

### Test case 2

input<br>
a=[90,8,11,3,2000,700,478] <br>

Output:<br>

No. of swaps= 8 <br>
No. of comparisions=12 <br>
Sorted Array is: <br>
3 8 11 90 478 700 2000<br>

### Test case 3

input<br>
a=[0,33,7000,344,-88,2000]<br>

output:<br>

No. of swaps= 6<br>
No. of comparisions=10<br>
Sorted Array is:<br>
-88 0 33 344 2000 7000<br>

## Output

<img width = 221 height = 27 src="../Insertion Sort/Images/input.png">
<img width = 385 height = 188 src="../Insertion Sort/Images/sort_output1.png">

def add_list(l):
    # The sum of an empty list is 0
    if l == []:
        return 0

    return l[0] + add_list(l[1:])


l = [1,2,3,4]

print(add_list(l)) # Should print 10

    print(f'Add {l[0]} to the sum of {l[1:]}')
    return l[0] + add_list(l[1:])

def quicksort(list):
    # One of our base cases is an empty list or list with one element
    if len(list) == 0 or len(list) == 1:
        return list

    # If we have a left list, a pivot point and a right list...
    left, pivot, right = partition(list)

    # Our sorted list looks like left + pivot + right, but sorted.
    # Pivot has to be in brackets to be a list, so python can concatenate all the elements to a single list
    return quicksort(left) + [pivot] + quicksort(right)

def partition(list):
    left = []
    pivot = list[0] # Or make random, as a stretch
    right = []

    for v in list[1:]:
        if v < pivot:
            left.append(v)
        else:
            right.append(v)

    return left, pivot, right

print(quicksort([]))
print(quicksort([1]))
print(quicksort([1,2]))
print(quicksort([2,1]))
print(quicksort([2,2]))
print(quicksort([5,3,9,4,8,1,7]))
print(quicksort([1,2,3,4,5,6,7]))
print(quicksort([9,8,7,6,5,4,3,2,1]))

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

def quicksort2(l, low, high):
    if len(l) == 0 or len(l) == 1:
        return l

    if low >= high:
        return l

    pivot_index = low

    # Partitioning
    for i in range(low, high):

        if l[i] < l[pivot_index]:
            # If i is less than pivot, we need to swap it with the item after the pivot
            l[i], l[pivot_index + 1] = l[pivot_index + 1], l[i]

            # Then we'll swap the pivot with the item after the pivot
            l[pivot_index], l[pivot_index + 1] = l[pivot_index + 1], l[pivot_index]

            # Update the pivot index:
            pivot_index += 1

    # Sort from low to the pivot index
    quicksort2(l, low, pivot_index)
    # Sort from the pivot index to high
    quicksort2(l, pivot_index + 1, high)

def in_place_quicksort(l):
    return quicksort2(l, 0, len(l))

print(in_place_quicksort([]))
print(in_place_quicksort([1]))
print(in_place_quicksort([1,2]))
print(in_place_quicksort([2,1]))
print(in_place_quicksort([2,2]))
print(in_place_quicksort([5,3,9,4,8,1,7]))
print(in_place_quicksort([1,2,3,4,5,6,7]))
print(in_place_quicksort([9,8,7,6,5,4,3,2,1]))

Our starting list is [5,3,9,4,8]. 

Checking against 5. Current list is [5, 3, 9, 4]. 

Checking against 3. Current list is [5, 3, 9, 4]. 

3 is less than 5, so we need to swap l[i] (3) with l[pivot_index + 1] (3).
Next, we will swap 5 with 3 and increase the pivot index from 0 to 1.
Now the current list is [3, 5, 9, 4] 

Checking against 9. Current list is [3, 5, 9, 4]. 

Checking against 4. Current list is [3, 5, 9, 4]. 

4 is less than 5, so we need to swap l[i] (4) with l[pivot_index + 1] (9).
Next, we will swap 5 with 4 and increase the pivot index from 1 to 2.
Now the current list is [3, 4, 5, 9] 


Splitting list to check quicksort([3, 4, 5, 9], 0, 2) and quicksort([3, 4, 5, 9], 3, 4). 


Checking against 3. Current list is [3, 4, 5, 9]. 

Checking against 4. Current list is [3, 4, 5, 9]. 



Splitting list to check quicksort([3, 4, 5, 9], 0, 0) and quicksort([3, 4, 5, 9], 1, 2). 

Checking against 4. Current list is [3, 4, 5, 9]. 



Splitting list to check quicksort([3, 4, 5, 9], 1, 1) and quicksort([3, 4, 5, 9], 2, 2). 

Checking against 9. Current list is [3, 4, 5, 9]. 



Splitting list to check quicksort([3, 4, 5, 9], 3, 3) and quicksort([3, 4, 5, 9], 4, 4). 

Our final sorted list is [3, 4, 5, 9]