Merge and Quicksort Sorting Algorithm Tutorial

When you first begin really learning about algorithms one of the first areas of discussion is sorting. There is a great reason for this, everyone sorts something at some point in the day but never really thinks about how they sort. Sorting is such a second nature to us that it all happens at a sub-conscience level. Before we jump straight into Merge and Quick Sort let’s just make sure what our goals are with algorithms. The first thought is that algorithms are all math, but in truth they are simple computer processes, or more simply put, a logical sequence of events.

Merge-sort and Quicksort are part of sorting algorithms that use a divide and conquer methodology. Rather than dealing with all the data at once which could result in very long run times, the data is recursively (repeatedly) divided until it is sorted and then combined.

Before we jump into the code let’s try to visualize this process.

Quicksort Animation

Quicksort breaks down into 4 steps.

  1. if the start position is equal to the end of the data set your done.
    • if p == r
  2. split the data along a pivot value
    • int pivot = numbers[low+(high-low)/2];
  3. proceed from either end of the array until the left side greater than the pivot value and the right side is less then the pivot value then swap (exchange) the values.
  4. recursively repeat this process until sorted.

Quicksort in C# source code

    public class QuickSortClass
    {
     	private static byte[] numbers;
        private static int size;

        public static void sort(byte[] array)
        {
            //Good practice to validate your array first
            if(array==null || array.Length < 2) return;
            numbers = array;
            size = numbers.Length;
            quickSort(0, size - 1);
        }

        private static void quickSort(int low, int high)
        {
            int i = low;
            int j = high;
            //find a random pivot value usually in the middle value of the array.
            int pivot = numbers[low + (high - low) / 2];

            // Divide the array into 2 parts logically
            while(i <= j)
            {
                //Moving from the left inward until the left value is greater than the pivot value.
                while(numbers[i]  pivot)
		{
		    j--;
		}
 
                if (i <= j)
                {
                    //Exchange the 2 values and continue to the next values.
                    exchange(i, j);
                    i++;
                    j--;
                } 
            }

	    //Recursively repeat this process until sorted	
            if(low < j)
            {
                quickSort(low, j);
            }
            if(i < high)
            {
                quickSort(i, high);
            }
        }

        private static void exchange(int i, int j)
        {
            byte temp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = temp;
        }
    }

Quicksort in Java source code

    public class QuickSortClass
    {
        private byte[] numbers;
        private int size;

        public void sort(byte[] array)
        {
	    if (array == null || array.length < 2) return;
            this.numbers = array;
            this.size = this.numbers.length;
            quicksort(0, size - 1);
        }

        private void quicksort(int low, int high)
        {
            int i = low;
            int j = high;

            int pivot = numbers[low + (high - low) / 2];

            while(i <= j)
            {
                while(numbers[i]  pivot)
		{
	            j--;
		}

                if (i <= j)
                {
                    exchange(i, j);
                    i++;
                    j--;
                } 
            }
            if(low < j)
            {
                quicksort(low, j);
            }
            if(i < high)
            {
                quicksort(i, high);
            }
        }

        private void exchange(int i, int j)
        {
            byte temp = this.numbers[i];
            this.numbers[i] = this.numbers[j];
            this.numbers[j] = temp;
        }
    }

Quicksort in Objective C source code

QuickSortClass.h
#import 

@interface QuickSortClass : NSObject 

	-(void)sortWithArray:(UInt8*) array ofLength:(UInt32) length;

@end  

QuickSortClass.m

#import "QuickSortClass.h"
@interface QuickSortClass()

	@property (nonatomic) UInt8* numbers
	@property (nonatomic) NSInteger size;
	
@end

@implementation

        -(void) sortWithArray:(UInt8*)array ofLength:length
        {
            if(array == null || length < 2) return;
            numbers = array;
            size = length;
            [self quickSortWithLow:0 andHigh: size - 1];
        }

        -(void) quickSortWithLow:(NSInteger) low andHigh: (NSInteger) high
        {
            NSInteger i = low;
            NSInteger j = high;

            NSInteger pivot = numbers[low + (high - low) / 2];

            while(i <= j)
            {
                while(numbers[i]  pivot)
		{
		    j--;
		}

                if (i <= j)
                {
                    [self exchangeValue:i withValue: j];
                    i++;
                    j--;
                } 
            }
            if(low < j)
            {
                [self quickSortWithLow:low andHigh: j];
            }
            if(i < high)
            {
                [self quickSortWithLow: i andHigh: high];
            }
        }

        -(void) exchangeValue:(NSInteger) i withValue:(NSInteger) j
        {
            byte temp = self.numbers[i];
            self.numbers[i] = self.numbers[j];
            self.numbers[j] = temp;
        }
@end

Some additional things to consider about Quicksort, while on average the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

 Merge Sort Animation

Merge-sort

Probably the most notable difference between the 2 is that Quicksort is able to apply this sorting in place with no additional memory.

Merge sort breaks down into 4 steps.

  1. if the start position is equal to the end of the data set, your done.
    • if p == r
  2. recursively divide the data into smaller and smaller groups.
    • int middle = low+(high-low)/2;
  3. sort individual groups
  4. merge the data back together.

Merge sort in C#

    public class MergeSort
    {
        private static byte[] numbers;
        private static byte[] helper;

        private static int size;

        public static void sort(byte[] array)
        {
            if(array == null || array.Length < 2) return;
            numbers = array;
            size = array.Length;
            helper = new byte[size];
            divideAndConquer(0, size - 1);
        }

        private static void divideAndConquer(int low, int high)
        {
            if(low < high)
            {
                int middle = low + (high - low) / 2;

                divideAndConquer(low, middle);
                divideAndConquer(middle + 1, high);

                merge(low, middle, high);
            }
        }

        private static void merge(int low, int middle, int high)
        {
            int i = low;
            for (i = low; i <= high; i++)
            {
                helper[i] = numbers[i];
            }

            i = low;
            int j = middle + 1;
            int k = low;

            while (i <= middle && j <= high)
            {
                if(helper[i] <= helper[j])
                {
                    numbers[k] = helper[i];
                    i++;
                }
                else
                {
                    numbers[k] = helper[j];
                    j++;
                }
                k++;
            }

            while(i<= middle)
            {
                numbers[k] = helper[i];
                k++;
                i++;
            }
        }
    }

Merge sort in Java

    public class MergeSort
    {
        private byte[] numbers;
        private byte[] helper;

        private int size;

        public void sort(byte[] array)
        {
            if(array == null || array.length < 2) return;
            this.numbers = array;
            this.size = array.length;
            this.helper = new byte[this.size];
            divideAndConquer(0, this.size - 1);
        }

        private void divideAndConquer(int low, int high)
        {
            if(low < high)
            {
                int middle = low + (high - low) / 2;

                divideAndConquer(low, middle);
                divideAndConquer(middle + 1, high);

                merge(low, middle, high);
            }
        }

        private void merge(int low, int middle, int high)
        {
            int i = low;
            for (i = low; i <= high; i++)
            {
                this.helper[i] = this.numbers[i];
            }

            i = low;
            int j = middle + 1;
            int k = low;

            while (i <= middle && j <= high)
            {
                if(this.helper[i] <= this.helper[j])
                {
                    this.numbers[k] = this.helper[i];
                    i++;
                }
                else
                {
                    this.numbers[k] = this.helper[j];
                    j++;
                }
                k++;
            }

            while(i<= middle)
            {
                this.numbers[k] = this.helper[i];
                k++;
                i++;
            }
        }
    }

Merge sort in Objective C

MergeSort.h
#import 
@interface MergeSort:NSObject

	-(void) sortWithArray:(UInt8*) array ofLength:(NSInteger)length;

@end

MergeSort.m

#import "MergeSort.h"

@interface MergeSort()

	@property (nonatomic) UInt8 *numbers;
	@property (nonatomic) UInt8 *helper;
	@property (nonatomic) NSInteger size;

@end

@implementation MergeSort
        -(void) sortWithArray:(UInt8 *) array withLength:(NSInteger) length
        {
            if(array == null || length < 2) return;
            self.numbers = array;
            self.size = length;
	    self.helper = malloc(length * sizeof(UInt8));
            [self divideAndConquerWithLow: 0 andHigh: this.size - 1];
	
            free(self.helper);
        }

        -(void) divideAndConquerWithLow:(NSInteger)low andHigh: (NSInteger) high
        {
            if(low < high)
            {
                NSInteger middle = low + (high - low) / 2;

                [self divideAndConquerWithLow:low andHigh: middle];
                [self divideAndConquerWithLow:middle + 1 andHigh: high];

                [self mergeWithLow:low middle:middle andHigh:high];
            }
        }

        -(void) mergeWithLow:(NSInteger) low middle:(NSInteger) middle andHigh: (NSInteger) high
        {
            NSInteger i = low;
            for (i = low; i <= high; i++)
            {
                self.helper[i] = self.numbers[i];
            }

            i = low;
            NSInteger j = middle + 1;
            NSInteger k = low;

            while (i <= middle && j <= high)
            {
                if(self.helper[i] <= self.helper[j])
                {
                    self.numbers[k] = self.helper[i];
                    i++;
                }
                else
                {
                    self.numbers[k] = self.helper[j];
                    j++;
                }
                k++;
            }

            while(i<= middle)
            {
                self.numbers[k] = self.helper[i];
                k++;
                i++;
            }
        }
    }

Merge sort mathematically has an average and worst-case performance of O(n log n) with space O(n).

Final Thoughts

What we see is that although Merge sort is a faster sorting method than Quicksort, merge sort requires a copy of the list being sorted. Most variations of Merge sort focus on reducing this by only work on chunks of data rather than the entire data set at once.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s