Blog

CreativeCoders

Blog/
­

Mergesort: An analysis

From my previous implementation of Mergesort, I did some research on the overall comparisons.

Run Expected logn*n \sum Comparisons \delta \delta%
a) 3*1’000 9’976
b) 4*10’000 133’616 13,39 * a)
c) 5*100’000  1’668’928 12,49 * b) -7,2%
d) 6*1’000’000 19’951’424 11,95 * c) -4,5%
e) 7*10’000’000 233’222’784 11,68 * d) -2,3%
f) 8*100’000’000 2’665’782’272 11,43 * e) -2,1%

Due to the 32bit memory addressing boundary ( 2^{32}-1 possible addresses), I couldn’t check any larger lists. However you can clearly convince yourself that Mergesort is bounded in the number of comparisons to O(c*n*logn), with  \lim\limits_{n \rightarrow \infty}{c} being a constant ~ 10 (see delta).

By |November 17th, 2015|Uncategorized|0 Comments

Mergesort

Most algorithms or problems you have to deal with in computer science at least at some point do need sorting. In order to find something efficiently, your data should better be sorted. Imagine you’d to lookup a phone number in an unsorted phone book…

Mergesort is a fast way to sort a set of numbers. But remember: in computer science everything can be translated to a number (any formal language or alphabet). In other words: You can use Mergesort to sort literally anything.

Often you stick to an easier to implement algorithm, Bubblesort. If you don’t have large data to sort, it’s much more convenient to use Bubblesort (\mathcal O(n^2)). In terms of speed, it doesn’t matter. But as you data gets bigger, you should switch to Mergesort, which worst-case running time is \mathcal O(n*logn).

Mergesort should be somewhere in the C-standard-libs. You don’t have to code it yourself. But that’s what the blog is all about 🙂 As I’m doing all of my code from scratch, I’m not sure if this code is correct. But it seems to be working.

// ------------------------------------------------------------------------
void MergeSort( int l[], int n ) {
	// base case: list of one element is sorted
	if ( n <= 1 ) return;

	// if n is odd, the "extra" element is set into l1 
	int odd = n % 2;
	
	// split l into 2 list of almost same size
	int half = n / 2;
	
	// mergesort needs extra space
	int* l1 = (int*)calloc( half + odd, sizeof(int) );
	int* l2 = (int*)calloc( half, sizeof(int) );

	// copy elements over
	memcpy( l1, &l[0], (half+odd) * sizeof(int) );
	memcpy( l2, &l[half+odd], half * sizeof(int) );

	// recursively sort both lists
	MergeSort( l1, half+odd );
	MergeSort( l2, half );

	// merge them into l
	int p1 = 0; int p2 = 0;
	for ( int i = 0; i < n; i++ ) {
		// smaller element is in l1 or l2 is already "empty"
		if ( (l1[p1] <= l2[p2] && p1 < (half+odd)) || p2 >= half ) {
			if ( p2 >= half ) l[i] = l1[p1];
			else l[i] = l1[p1];
			p1++;
		}
		// smaller element is in l2 or l1 "ran out of elements"
		else if ( (l1[p1] > l2[p2] && p2 < half) || p1 >= (half+odd) ) {
			if ( p1 >= (half+odd) ) l[i] = l2[p2];
			else l[i] = l2[p2];
			p2++;
		}
	}

	// cleanup
	free( l1 );
	free( l2 );
}
By |November 16th, 2015|Uncategorized|0 Comments

Welcome!

In this blog I’m gonna show you interesting algorithms and code snippets. My favorite programming language is C++, but I’m not restricted to it. I’m also interested in reversing with a focus on malware, computer games and bypassing/improving protection schemes.

Feel free to leave some comments, improvement, suggestions or questions.

By |November 16th, 2015|Uncategorized|0 Comments