DEV Community 👩‍💻👨‍💻

Pritesh Bhoi
Pritesh Bhoi

Posted on • Originally published at blog.bhylu.com

Sorting Terminology - Must Know

What is in-place sorting?

An in-place sorting algorithm uses consistent space for generating the output (modifies the given array most effective). It sorts the list most effective through enhancing the order of the elements within the list.

For example, Insertion Sort and Selection Sorts are in-place sorting algorithms as they do now no longer use any extra area for sorting the list and a typical implementation of Merge Sort is not in-region, additionally the implementation for counting type is not an in-place sorting algorithm.

so the auxiliary space complexity of non-in-place sorting algorithms is extended through O(N) where N is the quantity of elements on which sorting needs to be applied while for in-region algorithms it does not increase.

Types Of Sorting :

  • Internal Sorting
  • External Sorting

Sort Stability :

  • Stable Sort
  • Unstable Sort

Internal sorting:

When all data is placed in main memory or internal storage, the sorting is called internal sorting.
In internal sorting, the problem cannot accommodate entries beyond their size.

Example: heap sort, bubble sort, selection sort, quick sort, shell sort, insertion sort.

External sorting:

If all the data to be sorted cannot be put into memory at once, the sorting is called an external sorting . External Sorting is used for large amounts of data.
The Merge sort and its variations are commonly used for external sorting.
Some external storage storage , such as hard drives and CDs, are used for external sorting.

Example: Merge sort, Tag sort, Polyphase sort, Four tape sort, External radix sort, Internal merge sort, etc.

What is stable sorting?

When two same pieces of data appear in the same order on ordered data without changing their position, it is called stable sort.

Example: merge sort, insertion sort, bubble sort.

What is unstable sorting?

If two data appearing in a different order in the sorted data is called an unstable sort.
Example: quick sort, heap sort, shell sort.

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.