## Problem: Sorting Elements of an Array by Frequency

*Difficulty: Easy

Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.

If frequencies of two elements are same, print them in increasing order.

Input:

The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, …, AN denoting the elements of the array.
Output:

Print each sorted array in a seperate line. For each array its numbers should be seperated by space.
Constraints:

1 ≤ T ≤ 70
30 ≤ N ≤ 130
1 ≤ A [ i ] ≤ 60
Example:

Input:

1
5
5 5 4 6 4

Output:

4 4 5 5 6

Implementation: Python 2.7

```"""
@author: loctv
@time: 12:54PM January 5, 2017
"""

def get_frequency(data):
"""
Get frequency of each element in data
"""
frequency = {}
for value in data:
frequency[value] = frequency.setdefault(value, 0) + 1
temp = list(frequency.keys())
return temp, frequency

def merge_sort(data, frequency):
if len(data) == 1:
return data
left_side = merge_sort(data[:len(data)//2], frequency)
right_side = merge_sort(data[len(data)//2:], frequency)
sorted_data = merge(left_side, right_side, frequency)
return sorted_data

def merge(left, right, frequency):
result, left_count, right_count = [], 0, 0
while left_count < len(left) and right_count < len(right):
if frequency[left[left_count]] > frequency[right[right_count]]:
result.append(left[left_count])
left_count += 1
elif frequency[left[left_count]] < frequency[right[right_count]]:
result.append(right[right_count])
right_count += 1
else: #equal frequency
if left[left_count] < right[right_count]:
result.append(left[left_count])
left_count += 1
else:
result.append(right_count)
right_count += 1
while left_count < len(left):
result.append(left[left_count])
left_count += 1
while right_count < len(right):
result.append(right[right_count])
right_count += 1
return result

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
data = map(int, raw_input().strip().split())
temp, frequency = get_frequency(data)
temp = merge_sort(temp, frequency)
res = []
for _ in temp:
res.extend([_]*frequency[_])
print res

```