sort and restore a set of bytes in optimal form Challenge

For any given input Y of length >= 1024 bytes:


sort in ascending or descending order -- your choice
generate output Q, where Q = [sorted data] + [restore
information]
restore Y using Q as input


Sorting Example

 input: [2, 5, 119, 0, 1, 223, 0, 118, ...]
output: [0, 0, 1, 2, 5, 118, 119, 223, ...] + [restore information]


Restore Example

 input: [0, 0, 1, 2, 5, 118, 119, 223, ...] + [restore information]
output: [2, 5, 119, 0, 1, 223, 0, 118, ...]


Winning

The program that generates the least amount of information in order to restore to original state wins, however it must work within a reasonable amount of time on modern hardware, less than 10 minutes.

UPDATE 1

You may use any third party libraries that are open-source if you so desire.

UPDATE 2

The [restore information] size is measured in bytes, it's your choice what it contains.

UPDATE 3

In case it's not yet clear, the input Y is a stream of bytes, you shouldn't care what it contains, all you care is to sort the values of the bytes in the order you prefer while also generating the necessary data in order to restore to Y from Q.
Python

The restore information is just the original list.  n bytes of restore information for an n byte list.

def sort(Y):
  return (sorted(Y), Y)

def restore(Q):
  return Q[1]