<Table> Merge sort <Tr> <Td colspan="2"> An example of merge sort . First divide the list into the smallest unit ( 1 element ) , then compare each element with the adjacent list to sort and merge the two adjacent lists . Finally all the elements are sorted and merged . </Td> </Tr> <Tr> <Th> Class </Th> <Td> Sorting algorithm </Td> </Tr> <Tr> <Th> Data structure </Th> <Td> Array </Td> </Tr> <Tr> <Th> Worst - case performance </Th> <Td> O ( n log n ) </Td> </Tr> <Tr> <Th> Best - case performance </Th> <Td> <P> O ( n log n ) typical , </P> O ( n ) natural variant </Td> </Tr> <Tr> <Th> Average performance </Th> <Td> O ( n log n ) </Td> </Tr> <Tr> <Th> Worst - case space complexity </Th> <Td> О ( n ) total with O ( n ) auxiliary , O ( 1 ) auxiliary with linked lists </Td> </Tr> </Table>
the number of comparisons needed in the worst case by the merge sort algorithm will be
O ( n log n )