Sorting : Sorting Vasantha Vallinayagam
Senior Lecturer
Dept., of IT
National Engg., College, Kovilpatti
Tamil Nadu, India
Lecture outline : 2 CS 1151 Data Structures VV Lecture outline Simple sorts
bubble sort
selection sort
insertion sort
Complex sorts
merge sort
shell sort
quick sort
heap sort
Sorting : 3 CS 1151 Data Structures VV Sorting Sorting = putting objects in order in array/list.
one of the fundamental problems in computer science.
comparison-based sorting: must determine order through comparison operations on the input data:
<, >, compareTo, …
Sorting Types : 4 CS 1151 Data Structures VV Sorting Types Internal (In-Memory) Sorting: When the size of memory is bigger than that of file to be sorted!
External Sorting: When the size of file to be sorted is bigger than that of available memory!
1. Bubble sort : 1. Bubble sort
Bubble sort : 6 CS 1151 Data Structures VV Bubble sort bubble sort: orders a list of values by repetitively comparing neighboring elements and swapping their positions if necessary.
more specifically:
scan the list, exchanging adjacent elements if they are not in relative order; this bubbles the highest value to the top.
scan the list again, bubbling up the second highest value.
repeat until all elements have been placed in their proper order.
"Bubbling" largest element : 7 CS 1151 Data Structures VV Traverse a collection of elements
Move from the front to the end
"Bubble" the largest value to the end using pair-wise comparisons and swapping 5 12 35 42 77 101 1 2 3 4 5 6 Swap "Bubbling" largest element
"Bubbling" largest element : 8 CS 1151 Data Structures VV "Bubbling" largest element Traverse a collection of elements
Move from the front to the end
"Bubble" the largest value to the end using pair-wise comparisons and swapping 5 12 35 77 42 101 1 2 3 4 5 6 Swap
"Bubbling" largest element : 9 CS 1151 Data Structures VV "Bubbling" largest element Traverse a collection of elements
Move from the front to the end
"Bubble" the largest value to the end using pair-wise comparisons and swapping 5 12 77 35 42 101 1 2 3 4 5 6 Swap
"Bubbling" largest element : 10 CS 1151 Data Structures VV "Bubbling" largest element Traverse a collection of elements
Move from the front to the end
"Bubble" the largest value to the end using pair-wise comparisons and swapping 5 77 12 35 42 101 1 2 3 4 5 6 No need to swap
"Bubbling" largest element : 11 CS 1151 Data Structures VV "Bubbling" largest element Traverse a collection of elements
Move from the front to the end
"Bubble" the largest value to the end using pair-wise comparisons and swapping 5 77 12 35 42 101 1 2 3 4 5 6 Swap
"Bubbling" largest element : 12 CS 1151 Data Structures VV "Bubbling" largest element Traverse a collection of elements
Move from the front to the end
"Bubble" the largest value to the end using pair-wise comparisons and swapping 77 12 35 42 5 1 2 3 4 5 6 101 Largest value correctly placed
Bubble sort code : 13 CS 1151 Data Structures VV Bubble sort code void bubbleSort(int a[], int n) {
for (int i = 0; i a[j]) {
swap(a, j-1, j);
}
}
}
}
swap (int a[], int k, int l)
{
int temp = a[k];
a[k]= a[l];
a[l] = temp;
}
Bubble sort runtime : 14 CS 1151 Data Structures VV Bubble sort runtime Running time (# comparisons) for input size n:
# comparisons =
number of actual swaps performed depends on the data; out-of-order data performs many swaps
2. Selection sort : 2. Selection sort
Selection sort : 16 CS 1151 Data Structures VV Selection sort selection sort: orders a list of values by repetitively putting a particular value into its final position.
more specifically:
find the smallest value in the list.
switch it with the value in the first position.
find the next smallest value in the list.
switch it with the value in the second position.
repeat until all values are in their proper places.
Selection sort example : 17 CS 1151 Data Structures VV Selection sort example
Selection sort example 2 : 18 CS 1151 Data Structures VV Selection sort example 2
Selection sort code : 19 CS 1151 Data Structures VV Selection sort code void selectionSort(int a[], int n) {
for (int i = 0; i < n; i++) {
// find index of smallest element
int min = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
// swap smallest element with a[i]
swap(a, i, min);
}
}
Selection sort runtime : 20 CS 1151 Data Structures VV Selection sort runtime Running time for input size n:
in practice, a bit faster than bubble sort. Why?
3. Insertion sort : 3. Insertion sort
Insertion sort : 22 CS 1151 Data Structures VV Insertion sort insertion sort: orders a list of values by repetitively inserting a particular value into a sorted subset of the list.
more specifically:
consider the first item to be a sorted sublist of length 1.
insert the second item into the sorted sublist, shifting the first item if needed.
insert the third item into the sorted sublist, shifting the other items as needed.
repeat until all values have been inserted into their proper positions.
Insertion sort : 23 CS 1151 Data Structures VV Insertion sort Simple sorting algorithm.
n-1 passes over the array
At the end of pass i, the elements that occupied A[0]…A[i] originally are still in those spots and in sorted order. after
pass 2 after
pass 3 after
pass 1
Insertion Sort Example – Contd., : 24 CS 1151 Data Structures VV Insertion Sort Example – Contd., After pass 3 After pass 4 After pass 5 After pass 6 After pass 7
Insertion sort example 2 : 25 CS 1151 Data Structures VV Insertion sort example 2
Insertion sort code : 26 CS 1151 Data Structures VV Insertion sort code void insertionSort(int a[], int n) {
for (int i = 1; i 0 && a[j - 1] > temp) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
Insertion sort runtime : 27 CS 1151 Data Structures VV Insertion sort runtime worst case: reverse-ordered elements in array.
best case: array is in sorted ascending order.
average case: each element is about halfway in order.
Comparing sorts : 28 CS 1151 Data Structures VV Comparing sorts We've seen "simple" sorting algorithms. so far, such as:
selection sort
insertion sort
They all use nested loops and perform approximately n2 comparisons
They are relatively inefficient
Average case analysis : 29 CS 1151 Data Structures VV Average case analysis Given an array A of elements, an inversion is an ordered pair (i, j) such that i < j, but A[i] > A[j]. (out of order elements)
Assume no duplicate elements.
Theorem: The average number of inversions in an array of n distinct elements is n (n - 1) / 4.
Corollary: Any algorithm that sorts by exchanging adjacent elements requires O(n2) time on average.
Sorting practice problem : 30 CS 1151 Data Structures VV Sorting practice problem Consider the following array of int values.
[22, 11, 34, -5, 3, 40, 9, 16, 6]
(a) Write the contents of the array after 3 passes of the outermost loop of bubble sort.
(b) Write the contents of the array after 5 passes of the outermost loop of insertion sort.
(c) Write the contents of the array after 4 passes of the outermost loop of selection sort.
4. Merge sort : 4. Merge sort
Merge sort : 32 CS 1151 Data Structures VV Merge sort merge sort: orders a list of values by recursively dividing the list into half until each sub-list has one element, then recombining.
Invented by John von Neumann in 1945.
more specifically:
divide the list into two roughly equal parts.
recursively divide each part in half, continuing until a part contains only one element.
merge the two parts into one sorted list.
continue to merge parts as the recursion unfolds.
This is a "divide and conquer" algorithm.
Merge sort : 33 CS 1151 Data Structures VV Merge sort idea:
Divide the array into two halves.
Recursively sort the two halves (using merge sort).
Use merge to combine the two arrays. sort sort merge(0, n/2, n-1) mergeSort(0, n/2-1) mergeSort(n/2, n-1) Merge sort
Slide 34 : 34 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42
Slide 35 : 35 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42
Slide 36 : 36 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98
Slide 37 : 37 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98
Slide 38 : 38 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 Merge
Slide 39 : 39 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 23 Merge
Slide 40 : 40 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 23 98 Merge
Slide 41 : 41 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 23 98
Slide 42 : 42 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 Merge 23 98
Slide 43 : 43 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 14 Merge 23 98
Slide 44 : 44 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 45 Merge 23 98 14
Slide 45 : 45 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 Merge 98 45 14 23
Slide 46 : 46 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 Merge 98 14 14 23 45
Slide 47 : 47 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 Merge 23 14 14 23 98 45
Slide 48 : 48 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 Merge 23 98 45 14 14 23 45
Slide 49 : 49 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 Merge 23 98 45 14 14 23 45 98
Slide 50 : 50 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 23 98 45 14 14 23 45 98
Slide 51 : 51 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 23 98 45 14 14 23 45 98
Slide 52 : 52 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 Merge 23 98 45 14 14 23 45 98
Slide 53 : 53 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 6 Merge 23 98 45 14 14 23 45 98
Slide 54 : 54 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 67 Merge 23 98 45 14 6 14 23 45 98
Slide 55 : 55 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 23 98 45 14 67 6 14 23 45 98
Slide 56 : 56 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 14 23 45 98
Slide 57 : 57 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 33 23 98 45 14 67 6 14 23 45 98
Slide 58 : 58 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 42 23 98 45 14 67 6 33 14 23 45 98
Slide 59 : 59 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 45 98
Slide 60 : 60 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 6 42 33 14 23 45 98 6 67
Slide 61 : 61 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 6 33 14 23 45 98 6 33 67 42
Slide 62 : 62 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 6 42 33 14 23 45 98 6 33 42 67
Slide 63 : 63 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 45 98 6 33 42 67
Slide 64 : 64 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 23 45 98 33 42 67 14 6
Slide 65 : 65 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 23 45 98 6 42 67 6 14 33
Slide 66 : 66 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 45 98 6 42 67 6 14 23 33
Slide 67 : 67 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 98 6 42 67 6 14 23 45 33
Slide 68 : 68 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 98 6 33 67 6 14 23 33 45 42
Slide 69 : 69 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 98 6 33 42 6 14 23 33 42 45 67
Slide 70 : 70 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 45 6 33 42 6 14 23 33 42 45 98 67
Slide 71 : 71 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 45 98 6 33 42 67 6 14 23 33 42 45 67
Slide 72 : 72 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 Merge 23 98 45 14 67 6 42 33 14 23 45 98 6 33 42 67 6 14 23 33 42 45 67 98
Slide 73 : 73 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 67 45 23 14 6 33 98 42 45 23 14 98 23 98 45 14 67 6 33 42 67 6 33 42 23 98 45 14 67 6 42 33 14 23 45 98 6 33 42 67 6 14 23 33 42 45 67 98
Slide 74 : 74 CS 1151 Data Structures VV 67 45 23 14 6 33 98 42 6 14 23 33 42 45 67 98
Merge sort example 2 : 75 CS 1151 Data Structures VV Merge sort example 2
Merging two sorted arrays : 76 CS 1151 Data Structures VV merge operation:
Given two sorted arrays, merge operation produces a sorted array with all the elements of the two arrays Running time of merge: O(n), where n is the number of elements in the merged array.
when merging two sorted parts of the same array, we'll need a temporary array to store the merged whole. Merging two sorted arrays
Merge sort code : 77 CS 1151 Data Structures VV Merge sort code void mergeSort(int a[], int n) {
int temp[n] ;
mSort(a, temp, 0, n- 1);
}
void mSort(int a[], int temp[], int left, int right) {
if (left >= right) { // base case
return;
}
// sort the two halves
int mid = (left + right) / 2;
mSort(a, temp, left, mid);
mSort(a, temp, mid + 1, right);
// merge the sorted halves into a sorted whole
merge(a, temp, left, right);
}
Merge code : 78 CS 1151 Data Structures VV Merge code void merge(int a[], int temp[], int left, int right) {
int mid = (left + right) / 2;
int count = right - left + 1;
int l = left; // counter indexes for L, R
int r = mid + 1;
// main loop to copy the halves into the temp array
for (int i = 0; i < count; i++)
if (r > right) { // finished right; use left
temp[i] = a[l++];
} else if (l > mid) { // finished left; use right
temp[i] = a[r++];
} else if (a[l] < a[r]) { // left is smaller (better)
temp[i] = a[l++];
} else { // right is smaller (better)
temp[i] = a[r++];
}
// copy sorted temp array back into main array
for (int i = 0; i < count; i++) {
a[left + i] = temp[i];
}
}
Merge sort runtime : 79 CS 1151 Data Structures VV Merge sort runtime T(n) = O(n log n)
Sorting practice problem : 80 CS 1151 Data Structures VV Sorting practice problem Consider the following array of int values.
[22, 11, 34, -5, 3, 40, 9, 16, 6]
(e) Write the contents of the array after all the recursive calls of merge sort have finished (before merging).
5. Shell sort : 5. Shell sort
Shell sort description : 82 CS 1151 Data Structures VV Shell sort description shell sort: orders a list of values by comparing elements that are separated by a gap of >1 indexes.
a generalization of insertion sort.
invented by computer scientist Donald Shell in 1959.
based on some observations about insertion sort:
insertion sort runs fast if the input is almost sorted.
insertion sort's weakness is that it swaps each element just one step at a time, taking many swaps to get the element into its correct position.
Shell sort description – Contd., : 83 CS 1151 Data Structures VV Shell sort description – Contd., Shellsort is also known as diminishing increment sort.
The distance between comparisons decreases as the sorting algorithm runs until the last phase in which adjacent elements are compared.
Shell sort example : 84 CS 1151 Data Structures VV Shell sort example Idea: Sort all elements that are 5 indexes apart, then sort all elements that are 3 indexes apart, ...
Shell sort code : 85 CS 1151 Data Structures VV Shell sort code void shellSort(int a[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i = gap && temp < a[j - gap]) {
a[j] = a[j – gap];
j -= gap;
}
a[j] = temp;
}
}
}
6. Quick sort : 6. Quick sort
Quick sort : 87 CS 1151 Data Structures VV Quick sort quick sort: orders a list of values by partitioning the list around one element called a pivot, then sorting each partition.
invented by British computer scientist C.A.R. Hoare in 1960.
more specifically:
choose one element in the list to be the pivot (= partition element).
organize the elements so that all elements less than the pivot are to its left and all greater are to its right.
apply the quick sort algorithm (recursively) to both partitions.
Quick sort, continued : 88 CS 1151 Data Structures VV Quick sort, continued For correctness, it's okay to choose any pivot.
For efficiency, one of following is best case, the other worst case:
pivot partitions the list roughly into half
pivot is greatest or least element in list
Which case above is best?
We will divide the work into two methods:
quickSort – performs the recursive algorithm
partition – rearranges the elements into two partitions
Quick sort pseudo-code : 89 CS 1151 Data Structures VV Quick sort pseudo-code Let S be the input set.
If |S| = 0 or |S| = 1, then return.
Pick an element v in S. Call v the pivot.
Partition S – {v} into two disjoint groups:
S1 = {x S – {v} | x v}
S2 = {x S – {v} | x v}
Return { quicksort(S1), v, quicksort(S2) }
Quick sort illustrated : 90 CS 1151 Data Structures VV Quick sort illustrated
How to choose a pivot : 91 CS 1151 Data Structures VV How to choose a pivot first element
bad if input is sorted or in reverse sorted order
bad if input is nearly sorted
variation: particular element (e.g. middle element)
random element
even a malicious agent cannot arrange a bad input
median of three elements
choose the median of the left, right, and center elements
Partitioning algorithm : 92 CS 1151 Data Structures VV Partitioning algorithm The basic idea:
Move the pivot to the rightmost position.
Starting from the left, find an element pivot. Call the position i.
Starting from the right, find an element pivot. Call the position j.
Swap S[i] and S[j].
Quick sort code : 93 CS 1151 Data Structures VV Quick sort code void quickSort(int a[], int n) {
qSort(a, 0, n - 1);
}
void qSort(int a[], int min, int max) {
if (min >= max) { // base case; no need to sort
return;
}
// choose pivot -- we'll use the first element (might be bad!)
int pivot = a[min];
swap(a, min, max); // move pivot to end
// partition the two sides of the array
int middle = partition(a, min, max - 1, pivot);
// restore the pivot to its proper location
swap(a, middle, max);
// recursively sort the left and right partitions
qSort(a, min, middle - 1);
qSort(a, middle + 1, max);
}
Quick sort code, cont'd. : 94 CS 1151 Data Structures VV Quick sort code, cont'd. // partitions a with elements < pivot on left and
// elements > pivot on right;
// returns index of element that should be swapped with pivot
int partition(int a[], int i, int j, int pivot) {
i--; j++; // kludge because the loops pre-increment
while (true) {
// move index markers i,j toward center
// until we find a pair of mis-partitioned elements
do { i++; } while (i < j && a[i] < pivot);
do { j--; } while (i < j && a[j] > pivot);
if (i >= j) {
break;
} else {
swap(a, i, j);
}
}
return i;
}
Special cases : 95 CS 1151 Data Structures VV Special cases What happens when the array contains many duplicate elements?
What happens when the array is already sorted (or nearly sorted) to begin with?
Small arrays
Quicksort is slower than insertion sort when is N is small (say, N 20).
Optimization: Make |A| 20 the base case and use insertion sort algorithm on arrays of that size or smaller.
Quick sort runtime : 96 CS 1151 Data Structures VV Quick sort runtime Worst case: pivot is the smallest (or largest) element all the time.
Best case: pivot is the median
T(n) = O(n log n)
Quick sort runtime summary : 97 CS 1151 Data Structures VV Quick sort runtime summary O(n log n) on average.
O(n2) worst case.
Sorting practice problem : 98 CS 1151 Data Structures VV Sorting practice problem Consider the following array of int values.
[22, 11, 34, -5, 3, 40, 9, 16, 6]
(f) Write the contents of the array after all the partitioning of quick sort has finished (before any recursive calls).
Assume that the median of three elements (first, middle, and last) is chosen as the pivot.
Comparison of Sort Algorithms : 99 CS 1151 Data Structures VV Comparison of Sort Algorithms
Slide 100 : 100 CS 1151 Data Structures VV Queries ???
Thank U !!!