An NSArray category to merge multiple sorted NSArrays into one sorted NSArray (not arc compatible, yet?)

NSArray+MergeSorted.h

//
//  NSArray+MergeSorted.h
//  NSArray Merge Sorted Category
//
//  Created by Andrew Bennett on 31/05/12.
//  Copyright (c) 2012 Andrew Bennett. All rights reserved.
//

#import <Foundation/Foundation.h>

@interface NSArray(MergeSorted)

+(id) arraySortedWithComparator: (NSComparator) compare
               fromSortedArrays: (NSArray*) arrays, ... NS_REQUIRES_NIL_TERMINATION;
+(id) arraySortedWithComparator: (NSComparator) compare
        fromArrayOfSortedArrays: (NSArray*) array_array;

+(id) sortedArrayFromSortedArrays: (NSArray*) arrays, ... NS_REQUIRES_NIL_TERMINATION;
+(id) sortedArrayFromArrayOfSortedArrays: (NSArray*) array_array;

@end

NSArray+MergeSorted.m

//
//  NSArray+MergeSorted.m
//  NSArray Merge Sorted Category
//
//  Created by Andrew Bennett on 31/05/12.
//  Copyright (c) 2012 Andrew Bennett. All rights reserved.
//

#import "NSArray+MergeSorted.h"

@implementation NSArray(MergeSorted)

+(id) sortedArrayFromSortedArrays: (NSArray*) arrays, ...
{
    NSMutableArray * out_array;
    va_list vargs;

    id __unsafe_unretained array_list[16];
    NSUInteger count = 1;
    id object;

    array_list[0] = arrays;
    va_start(vargs, arrays);
    while ((object = va_arg(vargs,id)) != nil)
    {
        array_list[count] = object;
        ++count;
    }
    va_end(vargs);

    out_array = [NSArray arraySortedWithComparator: ^(id obj1, id obj2) {return [obj1 compare: obj2];}
                                  fromSortedArrays: array_list
                                             count: count];

    return out_array;
}
+(id) sortedArrayFromArrayOfSortedArrays: (NSArray*) array_array
{
    return [NSArray arraySortedWithComparator: ^(id obj1, id obj2) {return [obj1 compare: obj2];}
                      fromArrayOfSortedArrays: array_array];
}

+(id) arraySortedWithComparator: (NSComparator) compare
                      a_objects: (id __unsafe_unretained **) a_objects
                        a_index: (size_t*) a_index
                        a_count: (size_t*) a_count
                          count: (NSUInteger) count
                       capacity: (NSUInteger) capacity
{
    NSMutableArray * out_array;
    
    out_array = [[NSMutableArray alloc] initWithCapacity: capacity];
    for (NSUInteger i=0; i<capacity; ++i)
    {
        NSUInteger best_e = 0;
        id obj, best = nil;
        for (NSUInteger e=0; e<count; ++e)
        {
            
            if (a_index[e] < a_count[e])
            {
                obj = a_objects[e][a_index[e]];
                if (best == nil || compare(obj, best) != NSOrderedDescending)
                {
                    best_e = e;
                    best   = obj;
                }
            }
        }
        NSParameterAssert(best != nil);
        [out_array addObject: best];
        ++a_index[best_e];
    }

    return [out_array autorelease];
}

+(id) arraySortedWithComparator: (NSComparator) compare
               fromSortedArrays: (NSArray*) arrays, ...
{
    NSArray * out_array;
    va_list vargs;
    
    id __unsafe_unretained array_list[16];
    NSUInteger count = 1;
    id object;
    
    array_list[0] = arrays;
    va_start(vargs, arrays);
    while ((object = va_arg(vargs,id)) != nil)
    {
        array_list[count] = object;
        ++count;
    }
    va_end(vargs);

    out_array = [NSArray arraySortedWithComparator: compare
                                  fromSortedArrays: array_list
                                             count: count];

    return out_array;
}

+(id) arraySortedWithComparator: (NSComparator) compare
               fromSortedArrays: (NSArray* __unsafe_unretained * ) arrays
                          count: (NSUInteger) count
{
    NSArray * array, * out_array;
    NSUInteger capacity;

    id __unsafe_unretained * a_objects[16];
    size_t a_index[16], a_count[16];
    capacity = 0;

    NSParameterAssert(count < 16);

    for (NSUInteger i=0; i<count; ++i)
    {
        array = arrays[i];
        a_index[i]   = 0;
        a_count[i]   = array.count;
        a_objects[i] = (id __unsafe_unretained *) malloc(a_count[i] * sizeof(id));
        NSParameterAssert(a_count[i] != 0 || a_objects[i] != NULL);

        [array getObjects: a_objects[i]
                    range: NSMakeRange(0, a_count[i])];
        capacity += a_count[i];
    }

    out_array = [NSArray arraySortedWithComparator: compare
                                         a_objects: a_objects
                                           a_index: a_index
                                           a_count: a_count
                                             count: count
                                          capacity: capacity];
    for (NSUInteger e=0; e<count; ++e)
    {
        free(a_objects[e]);
    }

    return out_array;
}

+(id) arraySortedWithComparator: (NSComparator) compare
        fromArrayOfSortedArrays: (NSArray*) array_array
{
    NSArray * out_array, * array;
    NSUInteger capacity, count;

    id __unsafe_unretained **a_objects;
    size_t *a_index, *a_count;
    capacity = 0;
    count    = array_array.count;

    a_objects = (id __unsafe_unretained **) malloc(count * sizeof(id*));
    a_index   = malloc(count * sizeof(size_t));
    a_count   = malloc(count * sizeof(size_t));

    for (NSUInteger i=0; i<count; ++i)
    {
        array        = [array_array objectAtIndex: i];
        a_index[i]   = 0;
        a_count[i]   = array.count;
        a_objects[i] = (id __unsafe_unretained *) malloc(a_count[i] * sizeof(id));
        NSParameterAssert(a_count[i] != 0 || a_objects[i] != NULL);

        [array getObjects: a_objects[i]
                    range: NSMakeRange(0, a_count[i])];
        capacity += a_count[i];
    }

    out_array = [NSArray arraySortedWithComparator: (NSComparator) compare
                                         a_objects: a_objects
                                           a_index: a_index
                                           a_count: a_count
                                             count: count
                                          capacity: capacity];
    for (NSUInteger e=0; e<count; ++e)
    {
        free(a_objects[e]);
    }

    free(a_index);
    free(a_count);
    free(a_objects);

    return out_array;
}

@end