# [Libre-soc-bugs] [Bug 659] SVP64 demo / unit test of CRM data-dependent ffirst mode implementing insertion sort

bugzilla-daemon at libre-soc.org bugzilla-daemon at libre-soc.org
Wed Jul 21 13:15:40 BST 2021

```https://bugs.libre-soc.org/show_bug.cgi?id=659

--- Comment #1 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---

def median_of_medians(A, i):

#divide A into sublists of len 5
sublists = [A[j:j+5] for j in range(0, len(A), 5)]
medians = [sorted(sublist)[len(sublist)/2] for sublist in sublists]
if len(medians) <= 5:
pivot = sorted(medians)[len(medians)/2]
else:
#the pivot is the median of the medians
pivot = median_of_medians(medians, len(medians)/2)

#partitioning step
low = [j for j in A if j < pivot]
high = [j for j in A if j > pivot]

k = len(low)
if i < k:
return median_of_medians(low,i)
elif i > k:
return median_of_medians(high,i-k-1)
else: #pivot = k
return pivot

#Here are some example lists you can use to see how the algorithm works
#A = [1,2,3,4,5,1000,8,9,99]
#B = [1,2,3,4,5,6]
#print median_of_medians(A, 0) #should be 1
#print median_of_medians(A,7) #should be 99
#print median_of_medians(B,4) #should be 5

--
You are receiving this mail because:
You are on the CC list for the bug.
```