# Big Sorting

See the original problem on HackerRank.

Consider an array of numeric strings where each string is a positive number with anywhere from $$1$$ to $$10^6$$ digits. Sort the array's elements in non-decreasing, or ascending order of their integer values and print each element of the sorted array on a new line.

See Big Sorting on HackerRank.

## Solutions

We may be tempted to use arbitrary precision arithmetic - e.g. Big Integers. This is not needed and it's possibly slow to convert from/to the decimal number system.

Instead, we could note that if the numbers have a different number of digits then a lexicographical comparison does the job. Otherwise, the number with more digits is clearly bigger.

Thus, we could just read all the numbers as strings and sort them by using a comparison function that implements such an observation.

It's interesting to use different languages and see how to the customize the standard sort:

### Solution in C++

 1 2 3 4 5 6 7 8 9  int n, i; cin >> n; vector v(n); copy_n(istream_iterator(cin), n, begin(v)); sort(begin(v), end(v), [](auto& l, auto& r) { if (l.size() == r.size()) return l < r; return l.size() < r.size(); }); 

In this snippet, you can see that we use std::string::operator< that implements a lexicographical comparison.

### Solution in Bash

The simplicity of Bash is disarming:

 1  read line; sort -n 

### Solution in C#

  1 2 3 4 5 6 7 8 9 10 11 12 13  int n = Convert.ToInt32(Console.ReadLine()); string[] a = new string[n]; for (int i = 0; i < n; i++) a[i] = Console.ReadLine(); Array.Sort(a, (left, right) => { if (left.Length != right.Length) return left.Length - right.Length; else return string.CompareOrdinal(left, right); // left.CompareTo(right) is too slow }); for (int i = 0; i < n; i++) Console.WriteLine(a[i]); 

Differently from C++, here you see that C#‘s Sort wants a C-style comparison operator: when the method returns 0, it means that two objects sort the same. Negative value means the first object is smaller, positive value means the first object is bigger.

Very similar to C#: Java and Javascript.

### Solution in Ruby

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  n = gets.strip.to_i a = Array.new(n) for i in (0..n-1) a[i] = gets.strip end a.sort! do |left, right| if left.length != right.length left.length <=> right.length else left <=> right end end for i in (0..n-1) puts a[i] end 

Ruby uses the so-called spaceship operator.

We've worked on this challenge in these gyms: modena