 In sorting "n" objects, merge sort has an average and worst-case performance of O("n" log "n").If the running time of merge sort for a list of length "n" is "T"("n"), then the recurrence "T"("n") = 2"T"("n"/2) + "n" follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the "n" steps taken to merge the resulting two lists).The closed form follows from the master theorem for divide-and-conquer recurrences.