What do you mean by Sorting? Write the algorithm to sort using merge sort. Take a sample to explain your answer.

Sorting is a fundamental concept in computer science and is a method of arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order which can be numerical or lexicographical order. The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner.

Merge Sort is a type of sorting algorithm that follows the divide and conquer approach. It works by dividing the unsorted list into n sublists, each containing one element (a list of one element is considered sorted), and then repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

Here is the step by step approach to sort using merge sort:

1. Divide: Divide the unsorted list into n sublists, each containing one element.
2. Conquer: Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.

The algorithm can be written as follows:

function mergeSort(list)
    if list size is 0 or 1
        return list
    else
        divide the unsorted list into two sublists.
        left = mergeSort(left part of the list)
        right = mergeSort(right part of the list)
        result = merge(left, right)
        return result
    end if
end function

function merge(left, right)
    result = empty list
    while left is not empty and right is not empty
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
        end if
    end while
    if left is not empty then append the rest of left to result 
    if right is not empty then append the rest of right to result 
    return result
end function

Let's take an example to understand it better:

Consider the array A = [38, 27, 43, 3, 9, 82, 10]. The steps for performing merge sort are as follows:

1. Divide the unsorted list into two sublists. So, we have [38, 27, 43, 3] and [9, 82, 10].
2. Repeat the process for these two sublists. For [38, 27, 43, 3], we get [38, 27] and [43, 3]. For [9, 82, 10], we get [9] and [82, 10].
3. Continue this process until we get n lists. So, we have [38], [27], [43], [3], [9], [82], [10].
4. Start merging these lists while sorting them. So, [38, 27] becomes [27, 38], [43, 3] becomes [3, 43], and [82, 10] becomes [10, 82].
5. Continue this process to get [3, 27, 38, 43] and [9, 10, 82].
6. Merge these two lists to get the final sorted list [3, 9, 10, 27, 38, 43, 82].

So, the original array A = [38, 27, 43, 3, 9, 82, 10] is sorted to become [3, 9, 10, 27, 38, 43, 82] using merge sort.