merge_.py
No OneTemporary
Actions

Subscribers

None

File Metadata


	# 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