Q:

Sort NSMutableArray as threaded comments

I'm developing an iOS app for website, that uses disqus comment system.
So I'm trying to add feature for adding comments from this application.
My problem is that I don't know how to keep threaded structure, for example:  

Comment 1

Child 1.1

Child 1.1.1  
Child 1.1.2

Child 1.2
  
Child 1.2.1  

Comment 2
  
Child 2.1 

I found the solution in Java here java solution
It's almost works, but there is a big problem.
It makes the structure be like this:  

Comment 1

Child 1.1
Child 1.2
  
Child 1.2.1    
Child 1.1.1  
Child 1.1.2

Comment 2
  
Child 2.1 

It ruins the relations between parents and children.
When I add a new child, it only knows how many children its parent has,in other words how many brothers this child has. 
But there is no information that the brother of this child also has children, in other words when I add a new child it doesn't know that it has nephews. 

[threaded insertObject:child atIndex:i+[parent childCount]];

Please help me with this, I'm really stuck.
Here is the link, for test project link
And here is the code of sorting an array in objective-c  
+ (NSMutableArray *)makeThreadedCommentsOutOf:(NSMutableArray *)comments{

    NSMutableArray *threaded = [[NSMutableArray alloc] initWithCapacity:0];

    //An array used to hold processed comments which should be removed at the end of the cycle
    NSMutableArray *removeComments = [[NSMutableArray alloc] initWithCapacity:0];

    //get the root comments first (comments with no parent)
    for(int i = 0; i < [comments count]; i++){
        Comment *comment = [comments objectAtIndex:i];
        if([[comment parentId] isEqual:[NSNull null]]){
            comment.commentDepth = 0;//A property of Comment to hold its depth
            comment.childCount = 0;
            [threaded addObject:comment];
            [removeComments addObject:comment];
        }
    }

    if([removeComments count] > 0){
        //clear processed comments
        [comments removeObjectsInArray:removeComments];
        [removeComments removeAllObjects];
    }

    int depth = 0;
    //get the child comments up to a max depth of 10
    while([comments count] > 0 && depth <= 10){
        depth++;
        for(int j = 0; j< [comments count]; j++){
            Comment *child = [comments objectAtIndex:j];
            //check root comments for match
            for(int i = 0; i < [threaded count]; i++){
                Comment *parent = [threaded objectAtIndex:i];
                if([[parent commentId] isEqualToString:[child parentId]]){
                    [parent setChildCount:[parent childCount]+1 ];
                    [child setCommentDepth:depth+[parent commentDepth]];
                    [threaded insertObject:child atIndex:i+[parent childCount]];
                    [removeComments addObject:child];
                    continue;
                    //break;
                }
            }
        }
        if([removeComments count] > 0){
            //clear processed comments
            [comments removeObjectsInArray:removeComments];
            [removeComments removeAllObjects];
        }
    }    
    return threaded;
}

A:

Though you do not say so it appears that the comments in your array are already in temporal order; that is children occur after their parents and any siblings which come before them.
Your issue is that a comment does not come immediately after its previous sibling and all its children, or immediately after its parent if it is the first child.
You also do not say if comments know the commentID of their children, but you do say they know the commentID of their parent.
If any of the above is wrong then the rest of the answer probably won't help you. Assuming it is correct consider the following rough algorithm:

Create an empty array to hold all the root comments, those without parents.
Create an empty dictionary to map parent commentID's to arrays of child indexes in your array of comments.
Make one pass over your array of comments examining each comment in turn. If the comment has no parent add it to your array of root comments. If it has a parent add the comment's index to your dictionary which maps parent commentID's to arrays of child indexes.

With these two data structures you can easily traverse your comments in the order you wish. You step through your array of root comments, and for every comment you step through its children by stepping through the array of child indexes found in the dictionary. And so on, recursively.
If you want a "sorted" array you can create it using the above recursive algorithm, no need to try to calculate where to insert a comment within your existing mutable array - a challenging task as you found out - the comments will be added in the right order.
HTH
Addendum: Response To Comment
Recursion is a fundamental concept in programming. In pseudo-code outline the algorithm described above is:
visitAllDescendants(comment - the parent comment
                    allComments - indexed collection of all comments
                    parentToChildren - map from parentID to child comment indexes
                   )
{
   do something with comment - do whatever you want with the parent
   for every childIndex in order from parentToChildren[comment] do
      visitAllDescendants(allComments[childIndex], allComments, parentToChildren) - recursively process children
}

you will call this for each of your roots.
If your "do something with comment" is to add it to an ordered collection then this algorithm will produce a collection of comments in the order you want.

