merge_.py
View Options


			# array, start, middle, end
			def merge_count(A, s, m, end):
			# sizes
			nl = m - s
			nr = end - m

			# counter
			c = 0
			# output list
			out = []

			# indices
			l = s
			r = m

			# loop over and sort
			while l < nl or r < nr:
			if l == nl:
			# l can still be increased
			out.append(A[r])
			r += 1

			if l < nl: # exclude sentinel case
			#inversion detected
			#print("Inversion detected: (%f, %f)" % (L[l], R[r]))
			c += nl - l
			elif r == nr:
			# r can still be increased
			out.append(A[l])
			l += 1
			elif A[r] < A[l]:
			out.append(A[r])
			r += 1

			if l < nl: # exclude sentinel case
			#inversion detected
			#print("Inversion detected: (%f, %f)" % (L[l], R[r]))
			c += nl - l

			else:
			out.append(A[l])
			l += 1

			return c, out

master-raffo/algorithm/assignment/A1/merge_.pyf72f0429dcd1master