Skip to content

Instantly share code, notes, and snippets.

@sudheesh001
Created July 7, 2013 11:20
Show Gist options
  • Save sudheesh001/5943178 to your computer and use it in GitHub Desktop.
Save sudheesh001/5943178 to your computer and use it in GitHub Desktop.
Algorithm for Iterative Merge Sort

This is the algorithm you could be using for a Bottom Up, Non recursive method to write mergesort. Its faster. If you wish to see the time difference between both. Use the functions from the header file or to calculate and you'll see Iteration is faster. Though it could be slightly maddening near the end of the algorithm, give it a shot. Prior to invoking this algorithm run a sort for the first two elements of the array i.e array[0] and array[1] Time complexity O(nlogn)

FUNCTION MERGESORT(A, length)
  IF length < 2 THEN
		//RETURN everything because THE ARRAY IS ALREADY SORTED
		RETURN
	jump := 1
	WHILE jump < length DO
		startL := 0
		startR := jump
		WHILE startR + jump <= length DO
			MERGE(A, startL, startL + jump, startR startR + jump)
			startL := startR + jump
			startR := startL + jump
		IF startR < length THEN
			MERGE(A, startL, startL + jump, startR, length)
		jump := jump * 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment