TSORT - Editorial

editorial
, ,
1

Problem Link - Simple Sorting Practice Problem in Sorting

Problem Statement:

Given a list of numbers, you have to sort them in non decreasing order.

Approach:

You need to sort these integers in non-decreasing order. Sorting algorithms with time complexity better than O(N^2) are necessary because N can be as large as 10^6, so using efficient sorting algorithms like QuickSort - Quick Sort in Searching and Sorting Algorithms, MergeSort - Merge sort algorithm in Design and Analysis of Algorithms, or HeapSort - Heap Sort in Heaps (O(N log N)) is essential. Preferably the in-built sort functions which are optimized for such tasks.

Complexity:

  • Time Complexity: O(N log N) Using inbuilt sort function or any other sorting algorithms which has time complexity of O(N log N) as N<=10^6.
  • Space Complexity: O(N) using vector to store the numbers.