## Pattern: Sorting/Searching

### [148/Medium] Sort List

#### Problem

• Given the head of a linked list, return the list after sorting it in ascending order.

• Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

• Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

• Example 3:
Input: head = []
Output: []

• Constraints:
• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105
• Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

• See problem on LeetCode.

#### Solution: QuickSort

• Algorithm:
• Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.
• The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

• Why Quick Sort is preferred over MergeSort for sorting Arrays:
• Quick Sort in its general form is an in-place sort (i.e., it doesn’t require any extra storage) whereas merge sort requires $$O(n)$$ extra storage, $$n$$ denoting the array size which may be quite expensive. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both type of sorts have $$O(n\log{n})$$ average complexity but the constants differ. For arrays, merge sort loses due to the use of extra $$O(n)$$ storage space.
• Most practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of $$O(nLogn)$$. The worst case is possible in randomized version also, but worst case doesn’t occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice.
• Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.
• Quick Sort is also tail recursive, therefore tail call optimizations is done.
• Why MergeSort is preferred over QuickSort for Linked Lists?:
• In case of linked lists the case is different mainly due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike array, in linked list, we can insert items in the middle in $$O(1)$$ extra space and $$O(1)$$ time. Therefore merge operation of merge sort can be implemented without extra space for linked lists.
• In arrays, we can do random access as elements are continuous in memory. Let us say we have an integer (4-byte) array $$A$$ and let the address of A[0] be x then to access A[i], we can directly access the memory at ($$x + i*4$$). Unlike arrays, we can not do random access in linked list. Quick Sort requires a lot of this kind of access. In linked list to access $$i^{th}$$ index, we have to travel each and every node from the head to $$i^{th}$$ node as we don’t have continuous block of memory. Therefore, the overhead increases for quick sort. Merge sort accesses data sequentially and the need of random access is low.
• In partition(), we consider last element as pivot. We traverse through the current list and if a node has value greater than pivot, we move it after tail. If the node has smaller value, we keep it at its current position.
• In QuickSortRecur(), we first call partition() which places pivot at the correct position and returns pivot. After pivot is placed at correct position, we find tail node of left side (list before pivot) and recur for left list. Finally, we recur for right list.
class Node:
def __init__(self, val):
self.data = val
self.next = None

def __init__(self):

return

while curr.next:
curr = curr.next

newNode = Node(data)
curr.next = newNode

def printList(self,n):
while n:
print(n.data, end=" ")
n = n.next

''' takes first and last node,but do not
def paritionLast(self,start, end):
if start == end or not start or not end:
return start

pivot_prev = start
curr = start
pivot = end.data

'''iterate till one before the end,
no need to iterate till the end because end is pivot'''

while (start != end):
if (start.data < pivot):
pivot_prev = curr
temp = curr.data
curr.data = start.data
start.data = temp
curr = curr.next
start = start.next

'''swap the position of curr i.e.
next suitable index and pivot'''

temp = curr.data
curr.data = pivot
end.data = temp

''' return one previous to current because
current is now pointing to pivot '''
return pivot_prev

def sort(self, start, end):
# Base cases
if not start or start == end or start == end.next:
return

# split list and partition recurse
pivot_prev = self.paritionLast(start, end)
self.sort(start, pivot_prev)

'''
if pivot is picked and moved to the start,
that means start and pivot is same
so pick from next of pivot
'''
if pivot_prev and pivot_prev == start:
self.sort(pivot_prev.next, end)

# if pivot is in between of the list,start from next of pivot,
# since we have pivot_prev, so we move two nodes
elif pivot_prev and pivot_prev.next:
self.sort(pivot_prev.next.next, end)

if __name__ == "__main__":

while (n.next != None):
n = n.next


• which outputs:
Linked List before sorting
30 3 4 20 5
3 4 5 20 30

##### Complexity
• Time: $$O(n\log{n})$$ (average performance) and $$O(n^2)$$ (worst-case performance), where $$n$$ is the number of nodes in linked list.
• Space: $$O(\log{n})$$ (average performance) and $$O(n)$$ (worst-case performance).
• The worst case arises when the sort is not balanced. However it can be avoided by sorting the smaller sub-arrays first and then tail-recursing on the larger array. This improved version will have a worst case space complexity of $$O(\log{n})$$. Note that the tail recursion is internally implemented by most compilers and no extra code needs to be written for that.
• Merge sort has an average/worst case space complexity of $$O(n)$$ because the merge subroutine copies the array to a new array which requires $$O(n)$$ extra space.
###### When does the worst case of Quicksort occur?
• The worst case time complexity of a typical implementation of QuickSort is $$O(n^2)$$ which can be hit depending on the strategy for choosing pivot. In early versions of Quick Sort, where the picked pivot is always an extreme (smallest or largest) element, i.e., the leftmost (or rightmost) element is chosen as a pivot, the worst occurs in the following cases.
1. Array is already sorted in the same order.
2. Array is already sorted in reverse order.
3. All elements are the same (a special case of cases 1 and 2)
• Thus, the worst case of Quicksort happens when input array is sorted or reverse sorted and either first or last element is picked as pivot.
• Since these cases are very common to use cases, the problem can easily be solved by choosing either a random index for the pivot, choosing the middle index of the partition, or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quicksort has fewer chances to occur, but a worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as the pivot.
• Although randomized QuickSort works well even when the array is sorted, it is still possible that the randomly picked element is always extreme.

#### Solution: Insertion Sort

• Below is a simple insertion sort algorithm for a linked list:
• Create an empty result list.
• Traverse the given list, do the following for every node.
• Insert current node in sorted way in the result list.
• The main process here is sortedInsert() which is doing a sorted insert by inserting a new node at the appropriate position in the input list.
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None

# function to sort a singly linked list using insertion sort
sorted = None

# Traverse the given linked list and insert every
# node to sorted
while current:
# Store next for next iteration
next = current.next

# insert current in sorted linked list
sorted = sortedInsert(sorted, current)

# Update current
current = next

# function to insert a new_node in a list. Note that this
# function expects a pointer to head_ref as this can modify the
current = None

# Special case for the head end */

else:
# Locate the node before the point of insertion
while current.next and
current.next.data < new_node.data:
current = current.next

new_node.next = current.next
current.next = new_node

# Function to print linked list */
while temp:
print( temp.data, end = " ")
temp = temp.next

# A utility function to insert a node
# at the beginning of linked list
# allocate node
new_node = Node(0)

# put in the data
new_node.data = new_data

# link the old list off the new node

# move the head to point to the new node

# Driver program to test above functions
a = None
a = push(a, 5)
a = push(a, 20)
a = push(a, 4)
a = push(a, 3)
a = push(a, 30)

printList(a)

a = insertionSort(a)

printList(a)

• which outputs:
Linked List before sorting
30  3  4  20  5
3  4  5  20  30

##### Complexity
• Time: $$O(n)*O(n)=O(n^2)$$ since in the worst case, we might have to traverse all nodes of the sorted list for inserting a node. And there are $$n$$ such nodes.
• Space: $$O(1)$$ since no extra space is required depending on the size of the input. Thus space complexity is constant.

#### Solution: Top Down/Recursive Merge Sort; recursively split the list into two parts, merge the two resulting sorted lists

• Merge Sort:
• The problem is to sort the linked list in $$O(n \log n)$$ time and using only constant extra space. If we look at various sorting algorithms, Merge Sort is one of the efficient sorting algorithms that is popularly used for sorting the linked list. The merge sort algorithm runs in $$O}(n \log n)$$ time in all the cases. Let’s discuss approaches to sort linked list using merge sort.
• Quicksort is also one of the efficient algorithms with the average time complexity of $$O(n \log n)$$. But the worst-case time complexity is $$O}(n ^{2})$$ . Also, variations of the quick sort like randomized quicksort are not efficient for the linked list because unlike arrays, random access in the linked list is not possible in $${O}(1)$$ time. If we sort the linked list using quicksort, we would end up using the head as a pivot element which may not be efficient in all scenarios.
• In summary, merge sort is a divide-and-conquer algorithm that is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
• Intuition:
• Merge sort is a popularly known algorithm that follows the Divide and Conquer Strategy. The divide and conquer strategy can be split into 2 phases:
• Divide phase: Divide the problem into subproblems.
• Conquer phase: Repeatedly solve each subproblem independently and combine the result to form the original problem.
• The Top Down approach for merge sort recursively splits the original list into sublists of equal sizes, sorts each sublist independently, and eventually merge the sorted lists. Let’s look at the algorithm to implement merge sort in Top Down Fashion.
• Algorithm:
• The algorithm is as follows:
• Divide phase: Recursively split the original list into two halves. The split continues until there is only one node in the linked list. To split the list into two halves, we find the middle of the linked list using the Fast and Slow pointer approach as mentioned in Find Middle Of Linked List.
• Merge phase: Recursively sort each sublist and combine it into a single sorted list. (Merge Phase). This is similar to the problem Merge two sorted linked lists
• The process continues until we get the original list in sorted order.
• For the linked list = [10,1,60,30,5], the following figure illustrates the merge sort process using a top down approach.

• Let the head be the first node of the linked list to be sorted and headRef be the pointer to head. Note that we need a reference to head in MergeSort() as the below implementation changes next links to sort the linked lists (not data at the nodes), so the head node has to be changed if the data at the original head is not the smallest value in the linked list.
MergeSort(headRef)
1) If the head is NULL or there is only one element in the Linked List
then return.
2) Else divide the linked list into two halves.
FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
MergeSort(a);
MergeSort(b);
4) Merge the sorted a and b (using SortedMerge())

# Python3 program to merge sort of linked list

# create Node using class Node.
class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

# push new value to linked list
# using append method
def append(self, new_value):

# Allocate new node
new_node = Node(new_value)

# if head is None, initialize it to new node
return
while curr_node.next:
curr_node = curr_node.next

# Append the new node at the end
curr_node.next = new_node

def sortedMerge(self, a, b):
result = None

# Base cases
if not a:
return b
if not b:
return a

# pick either a or b and recur..
if a.data <= b.data:
result = a
result.next = self.sortedMerge(a.next, b)
else:
result = b
result.next = self.sortedMerge(a, b.next)
return result

# Base case if head is None

# get the middle of the list
middle = self.getMiddle(h)
middleNext = middle.next

# set the next of middle node to None
middle.next = None

# Apply mergeSort on left list

# Apply mergeSort on right list
right = self.mergeSort(middleNext)

# Merge the left and right lists
sortedList = self.sortedMerge(left, right)
return sortedList

# Utility function to get the middle
# using The Tortoise and The Hare approach

while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

return slow

# Utility function to print the linked list
print(' ')
return

while curr_node:
print(curr_node.data, end = " ")
curr_node = curr_node.next

print(' ')

# Driver Code
if __name__ == '__main__':

# Let us create a unsorted linked list
# to test the functions created.
# The list shall be a: 2->3->20->5->10->15
li.append(15)
li.append(10)
li.append(5)
li.append(20)
li.append(3)
li.append(2)

# Apply merge Sort

• which outputs:
Sorted Linked List is:
2 3 5 10 15 20

##### Complexity
• Time: $$O(n\log{n})$$ (both average and worst-case performance), where $$n$$ is the number of nodes in linked list. The algorithm can be split into two phases, split and merge.
• Let’s assume that $$n$$ is power of 2. For n = 16, the split and merge operation in Top Down fashion can be visualized as follows:
• Split:
• The recursion tree expands in form of a complete binary tree, splitting the list into two halves recursively. The number of levels in a complete binary tree is given by $$\log_{2} n$$. For $$n=16$$, number of splits = $$\log_{2} 16 = 4$$.
• Merge:
• At each level, we merge $$n$$ nodes which takes $$\mathcal{O}(n)$$ time. For $$n = 16$$, we perform merge operation on 16 nodes in each of the 44 levels.
• So the time complexity for split and merge operation is $$\mathcal{O}(n \log n)$$.
• Space: $$O(n\log{n})$$, where $$n$$ is the number of nodes in linked list. Since the problem is recursive, we need additional space to store the recursive call stack. The maximum depth of the mergeSort() recursion tree is $$\log n$$ and the maximum depth of the sortedMerge() recursion tree is $$n$$.

#### Solution: Bottom Up/Iterative Merge Sort (better space complexity); recursively split the list into two parts, merge the two resulting sorted lists

• Intuition:
• The Top Down Approach for merge sort uses $$\mathcal{O}(\log n)$$ extra space due to recursive call stack. Let’s understand how we can implement merge sort using constant extra space using Bottom Up Approach.
• The Bottom Up approach for merge sort starts by splitting the problem into the smallest subproblem and iteratively merge the result to solve the original problem.
• First, the list is split into sublists of size 1 and merged iteratively in sorted order. The merged list is solved similarly.
• The process continues until we sort the entire list.
• This approach is solved iteratively and can be implemented using constant extra space. Let’s look at the algorithm to implement merge sort in Bottom Up Fashion.
• Algorithm:
• mergeSort():
1. If the size of the linked list is 1 then return the head.
2. Find mid using The Tortoise and The Hare Approach
3. Store the next of mid in b, i.e., the right sub-linked list.
4. Now make the next midpoint None.
5. Recursively call mergeSort() on both left and right sub-linked list and store the new head of the left and right linked list.
6. Call sortedMerge() given the arguments new heads of left and right sub-linked lists and store the final head returned after merging.
• merge(a, b):
1. Create a dummy node with fake data (say -1), say result, to store the merged list after sorting in its next and store a dummy node in it.
2. Take a pointer temp and assign merge to it.
3. If the data of a is less than the data of b, then, store a in next of temp and move a to the next of a.
4. Else store b in next of temp and move b to the next of b.
5. Move temp to the next of temp.
6. Repeat steps 3, 4 and 5 until a is not equal to None and b is not equal to None.
7. Now add any remaining nodes of the first or the second linked list to the merged linked list.
8. Return the next of result (that will ignore the dummy node and return the head of the final merged linked list)
• For the linked list = [10,1,30,2,5], the following figure illustrates the merge sort process using a Bottom Up approach.
# Node Class
class Node:
def __init__(self, key):
self.data = key
self.next = None

def __init__(self):

# Function to merge sort
def mergeSort(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Base case if head is None

# get the middle of the list
middleNext = middle.next

# set the next of middle node to None
middle.next = None

# Apply mergeSort on left list

# Apply mergeSort on right list
right = self.mergeSort(middleNext)

# Merge the left and right lists
sortedList = self.sortedMerge(left, right)
return sortedList

# Function to merge two linked lists
def sortedMerge(self, a, b):
# Base cases
if not a:
return b
if not b:
return a

# dummy node
result = Node(-1)
temp = result

# while a is not null and b
# is not None
while a and b:
if a.data < b.data:
temp.next = a
a = a.next
else:
temp.next = b
b = b.next
temp = temp.next

# while a is not null
while a:
temp.next = a
a = a.next
temp = temp.next

# while b is not null
while b:
temp.next = b
b = b.next
temp = temp.next

return result.next

# Utility function to get the middle
# using The Tortoise and The Hare approach

while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

return slow

# Function to print list

# Driver Code
temp.next = Node(10);
temp = temp.next;
temp.next = Node(5);
temp = temp.next;
temp.next = Node(20);
temp = temp.next;
temp.next = Node(3);
temp = temp.next;
temp.next = Node(2);
temp = temp.next;

# Apply merge Sort


• which outputs:
Sorted Linked List is:
2 3 5 7 10 20

##### Complexity
• Time: $$O(n\log{n})$$ (both average and worst-case performance), where $$n$$ is the number of nodes in linked list. Let’s analyze the time complexity of each step:
• Count Nodes: Get the count of number nodes in the linked list requires $$\mathcal{O}(n)$$ time.
• Split and Merge: This operation is similar to Approach 1 and takes $$\mathcal{O}(n \log n)$$ time. For $$n = 16$$, the split and merge operation in Bottom Up fashion can be visualized as follows
• This gives us total time complexity as $$\mathcal{O}(n)$$ + $$\mathcal{O}(n \log n)$$ = $$\mathcal{O}(n \log n)$$.
• Space: O(\log{n}) for mergSort() recursion. Also, note that storing the reference pointers tail, nextSubList etc. only uses constant space.

### [912/Medium] Sort an Array

#### Problem

• Given an array of integers nums, sort the array in ascending order.

• Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

• Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

• Constraints:
• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104
• Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

• See problem on LeetCode.

#### Solution: QuickSort

• Algorithm:
• Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.
• The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

#### Recursive QuickSort

• Pseudo Code for recursive QuickSort function:
/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);  // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}


##### Partition Algorithm
• There can be many ways to do partition, following pseudo code adopts the method given in CLRS book. The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element.
/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);  // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}

##### Pseudo code for partition()
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
partition (arr[], low, high)
{
// pivot (Element to be placed at right position)
pivot = arr[high];

i = (low - 1)  // Index of smaller element and indicates the
// right position of pivot found so far

for (j = low; j <= high- 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++;    // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}

##### Illustration of partition()
arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6

low = 0, high =  6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1

Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j
// are same

j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30

j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped

We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot)
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped

Now 70 is at its correct place. All elements smaller than
70 are before it and all elements greater than 70 are after
it.

• Why Quick Sort is preferred over MergeSort for sorting Arrays:
• Quick Sort in its general form is an in-place sort (i.e., it doesn’t require any extra storage) whereas merge sort requires $$O(n)$$ extra storage, $$n$$ denoting the array size which may be quite expensive. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both type of sorts have $$O(n\log{n})$$ average complexity but the constants differ. For arrays, merge sort loses due to the use of extra $$O(n)$$ storage space.
• Most practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of $$O(nLogn)$$. The worst case is possible in randomized version also, but worst case doesn’t occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice.
• Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.
• Quick Sort is also tail recursive, therefore tail call optimizations is done.
• Why MergeSort is preferred over QuickSort for Linked Lists?:
• In case of linked lists the case is different mainly due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike array, in linked list, we can insert items in the middle in $$O(1)$$ extra space and $$O(1)$$ time. Therefore merge operation of merge sort can be implemented without extra space for linked lists.
• In arrays, we can do random access as elements are continuous in memory. Let us say we have an integer (4-byte) array $$A$$ and let the address of A[0] be x then to access A[i], we can directly access the memory at ($$x + i*4$$). Unlike arrays, we can not do random access in linked list. Quick Sort requires a lot of this kind of access. In linked list to access $$i^{th}$$ index, we have to travel each and every node from the head to $$i^{th}$$ node as we don’t have continuous block of memory. Therefore, the overhead increases for quick sort. Merge sort accesses data sequentially and the need of random access is low.
class SortArray:
def sortArray(self, nums: List[int]) -> List[int]:
self.quicksort(nums, 0, len(nums)-1)
return nums

# Function to perform quicksort
def quick_sort(self, nums, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = self.partition(nums, low, high)

# Recursive call on the left of pivot
self.quick_sort(nums, low, pi - 1)

# Recursive call on the right of pivot
self.quick_sort(nums, pi + 1, high)

# Function to find the partition position
def partition(self, nums, low, high):

# Choose the rightmost element as pivot
pivot = nums[high]

# Pointer for greater element
i = low - 1

# Traverse through all elements
# compare each element with pivot
for j in range(low, high):
if nums[j] <= pivot:
# If element smaller than pivot is found
# swap it with the greater element pointed by i
i += 1

# Swapping element at i with element at j
nums[i], nums[j] = nums[j], nums[i]

# Swap the pivot element with the greater element specified by i
nums[i + 1], nums[high] = nums[high], nums[i + 1]

# Return the position from where partition is done
return i + 1

# Driver code
nums = [10, 7, 8, 9, 1, 5]
SortArray().sortArray(nums)
# or SortArray().quick_sort(nums, 0, len(nums) - 1)

print(f'Sorted array: {nums}')

• which outputs:
Sorted array:
1 5 7 8 9 10

##### Complexity
• Time: $$O(n\log{n})$$ (average performance) and $$O(n^2)$$ (worst-case performance), where $$n$$ is the number of nodes in linked list.
• Space: $$O(\log{n})$$ (average performance) and $$O(n)$$ (worst-case performance).
• The worst case arises when the sort is not balanced. However it can be avoided by sorting the smaller sub-arrays first and then tail-recursing on the larger array. This improved version will have a worst case space complexity of $$O(\log{n})$$. Note that the tail recursion is internally implemented by most compilers and no extra code needs to be written for that.
• Merge sort has an average/worst case space complexity of $$O(n)$$ because the merge subroutine copies the array to a new array which requires $$O(n)$$ extra space.
###### When does the worst case of Quicksort occur?
• The worst case time complexity of a typical implementation of QuickSort is $$O(n^2)$$ which can be hit depending on the strategy for choosing pivot. In early versions of Quick Sort, where the picked pivot is always an extreme (smallest or largest) element, i.e., the leftmost (or rightmost) element is chosen as a pivot, the worst occurs in the following cases.
1. Array is already sorted in the same order.
2. Array is already sorted in reverse order.
3. All elements are the same (a special case of cases 1 and 2)
• Thus, the worst case of Quicksort happens when input array is sorted or reverse sorted and either first or last element is picked as pivot.
• Since these cases are very common to use cases, the problem can easily be solved by choosing either a random index for the pivot, choosing the middle index of the partition, or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quicksort has fewer chances to occur, but a worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as the pivot.
• Although randomized QuickSort works well even when the array is sorted, there is still possible that the randomly picked element is always extreme.