Not identical to insertion sort in array


  • 0
    J

    In inserttion sort, there is one scan on the (partially) sorted sub-sequence.

    When we implement the sort on an array, we perform the scan from the largest ele to the first one. Because we can move the eles consecutively with in this scan.

    When implement the algorithm on a linked list, one the one hand, we don't need to move the elements in the partially sorted sub-sequence; on the other hand, to scan backward is expensive, requiring a stack. Simply scan forward from the head solves the problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.