Time complexity O(log N)

Uses auxiliary memory.

Time complexity O(N log N)

Has two stages: elements recursively are divided into two parts, then parts are merged in sorted way.

Sorting performance time depends on the selection of

gap.

Recursively one element is selected and other elements are placed to the left or right of that element.

Uses insertion sort as subroutine.