# Sort Big List Dates

#### Mary is a party-loving girl of the 21st Generation. She loves to attend parties and events with her family and friends. But she is terrible at remembering the dates of these events.

#### Mary has a list of dates of these events. Can you help her sort the list of dates to be easier for Mary to track the parties?

#### You are given an array ‘dates’ consisting of ‘N’ dates. You have to sort this array and print the array in sorted order.

##### For example:

```
If dates= [ [13,6,2007] , [2,6,2001] , [10,8,2019] , [1,6,2007] ]
Sorted Order of Dates will be :
dates = [ [ 2,6,2001] , [1,6,2007] , [13,6,2007] ]
```

##### Input Format:

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N,’ denoting the number of dates in the array.
The Next ‘N’ lines of each test case have three integers corresponding to date, month, and year.
```

##### Output Format:

```
For each test case, print ‘N’ lines for the sorted list elements, each line has three integers corresponding to date, month, and year.
Print the output of each test case in a separate line.
```

##### Note:

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 10
1 <= N <= 10^6
1 <= dates[i][0] <= 31
1 <= dates[i][1] <=12
2000 <= dates[i][2] <=2099
Time limit: 1 sec
```

In this approach, we will sort the array using Inbuild Sort with the help of a Comparator.

A Comparator is a custom compare function that decides the order of sorting by conditions defined by the programmer. It takes two arguments of the same datatype as the list element and returns a value whether the first argument will appear in the sorted array first or the second parameter. The Comparator will help us decide the relative positioning of elements in the sorted array.

**Algorithm:**

- We will define a comparator function with two dates,
**date1**and**date2,**as parameters.- First, we will compare by year, and if
**date1[2]**is less than**date2[2]**, then in the sorted list,**date2**should appear after**date1**. - If
**date1[2]**is greater than**date2[2]**, then in the sorted list,**date1**should appear after**date2**. - If the year is equal, we will compare by month, and if
**date1[1]**is less than**date2[1]**, then in the sorted list,**date2**should appear after**date1**. - If
**date1[1]**is greater than**date2[1]**, then in the sorted list,**date1**should appear after**date2**. - If the month is equal, we will compare by day, and if
**date1[0]**is less than**date2[0]**, then in the sorted list,**date2**should appear after**date1**. - If
**date1[0]**is greater than**date2[0]**,then in sorted list**date1**should appear after**date2**.

- First, we will compare by year, and if
- Call the inbuilt sort function with the comparator and sort the list.
- In the end, we will return the sorted array.

In this approach, we will use Counting Sort to sort the array. The Counting Sort is a non-comparison-based sorting method with linear time complexity. It is usually used with arrays whose values lie in a particular range. It simply counts each element's occurrences and then rearranges the array according to the frequencies.

**Algorithm:**

**Counting Sort:**- Make a function for implementing
**countSort(dates, par, maxVal)**, where**dates**are the given array,**par**is the parameter used for sorting, and**maxValue**is the maximum value of the parameter. - Initialize an array to store the frequency of all elements in the array.
- For each element in the array, do
**freq[i]**=**freq[i]**+**freq[i-1]**to find the index of the element in the sorted array. - Initialize a Sorted Array and use this frequency array to build up our sorted array.
- Copy the sorted array to the original array.

- Make a function for implementing
- We will first sort by day by updating
**dates**as**countSort(dates, 0, 31)**using this counting sort function. - We will now sort by month by updating
**dates**as**countSort(dates, 1, 12).** - We will now sort by year by updating
**dates**as**countSort(dates, 2, 2100).**

In the end, we will return the sorted array **dates**.