Data Structures and Algorithms for Beginners
About Lesson

Sorting is the process of arranging a list of elements in ascending or descending order. Sorting can be broken down into two categories:

  • Internal Sorting

    The computer’s main memory is used for internal sorting. As a result, it can take advantage of the random access feature of the main memory.

    The elements to be sorted are stored in an integer array. Various sorting algorithms can be used to sort these elements.

  • External Sorting

    Secondary storage is used for external sorting. When there is too much data to sort in memory, external sorting becomes necessary.

    The move of data from secondary storage to main memory should always be done by moving a set of contiguous elements.

  • Simple sorting algorithms such as bubble sort and insertion sort take O (n2) time to sort n elements.
  • Complex algorithms such as quick sort, merge sort, and heap sort take O (n log n) time to sort n elements.
  • The bubble sort, the insertion sort, and the merge sort are stable sorting algorithms. While the quick sort and heap sort are unstable.
  • The algorithm is said to be stable if after sorting, identical elements appear in the same sequence as in the original unsorted list.