Quicksort.m (Quicksort GCD Test)

//
//  QuickSort.m
//  Quicksort
//
//  Created by Craig Otis on 11/27/11.
//  Copyright (c) 2011 Home. All rights reserved.
//

#import "QuickSort.h"

@implementation QuickSort

+ (NSArray *)sort:(NSMutableArray *)input useGCD:(BOOL)useGCD {
    if ([input count] <= 1) {
        return input;
    }
    // Find a pivot, we just pick the middle
    NSUInteger pivotIndex = [input count] / 2;
    NSNumber *pivotObj = [input objectAtIndex:pivotIndex];
    int pivot = [pivotObj intValue];

    // Create empty less/greater arrays
    NSMutableArray *less = [[NSMutableArray alloc] init];
    NSMutableArray *greater = [[NSMutableArray alloc] init];

    // Populate less/greater arrays
    for (NSUInteger idx = 0; idx < [input count]; idx++) {
        if (idx == pivotIndex) {
            continue;
        }
        if ([[input objectAtIndex:idx] intValue] <= pivot) {
            [less addObject:[input objectAtIndex:idx]];
        } else {
            [greater addObject:[input objectAtIndex:idx]];
        }
    }

    // Merge the less/greater arrays, with pivot in the center
    NSMutableArray *concat = [[NSMutableArray alloc] init];
    if (useGCD) {
        // Create semaphore and sort the left side
        dispatch_semaphore_t lessSem = dispatch_semaphore_create(1);
        __block NSArray *lessSorted = nil;

        dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), ^{
            lessSorted = [QuickSort sort:less useGCD:useGCD];
            dispatch_semaphore_signal(lessSem);
        });

        // Create semaphore and sort the right side
        dispatch_semaphore_t moreSem = dispatch_semaphore_create(1);
        __block NSArray *moreSorted = nil;

        dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), ^{
            moreSorted = [QuickSort sort:greater useGCD:useGCD];
            dispatch_semaphore_signal(moreSem);
        });

        // Wait for both sides to finish sorting
        dispatch_semaphore_wait(lessSem, DISPATCH_TIME_FOREVER);
        dispatch_semaphore_wait(moreSem, DISPATCH_TIME_FOREVER);


        // Merge
        [concat addObjectsFromArray:lessSorted];
        [less release];
        [concat addObject:pivotObj];
        [concat addObjectsFromArray:moreSorted];
        [greater release];
    } else {
        // Merge
        [concat addObjectsFromArray:[QuickSort sort:less useGCD:useGCD]];
        [less release];
        [concat addObject:pivotObj];
        [concat addObjectsFromArray:[QuickSort sort:greater useGCD:useGCD]];
        [greater release];
    }
    return [concat autorelease];
}

+ (BOOL)testArray:(NSArray *)input {
    int last = INT_MIN;
    for (int i = 0; i < [input count]; i++) {
        int val = [[input objectAtIndex:i] intValue];
        if (val < last) {
            return NO;
        }
        last = val;
    }
    return YES;
}

@end