알고 계시겠지만 소팅은 제일 어려운 문제중에 하나입니다.

질문하신 것을 정리하면
  1. 현재사용하고 있는 advstringgrid를 대신할 수 있는 2차원배열의 정렬기법
  2. 정렬되기전에 원래의 인덱스를 확인할 수 있는 기법
인거 같습니다.

정렬할 자료가 많다면 새로운 방식의 정렬기법을 개발하는 것도 필요하겠지만 대부분 소팅기법이
퀵소트를 사용하니까 별다른 속도개선이 기대되지는 않습니다.
그리고 두가지 질문인데 답변은 하나만 해도 될 것 같습니다. 정렬전의 인덱스를 확인한다면 해당
하는 셀끼리 서로 교환해주면 되겠죠.
정확하게 검증해본 것은 아니지만 데이타 갯수가 많아지므로(천단위이상) 정렬에 소요되는 시간보다는
그리드에 출력하는데 사용되는 시간이 더 많아지기 때문에 느리다고 느끼는거 같습니다.

답변 2. 정렬할 때 인덱스를 포함한 자료도 같이 정렬시켜줍니다.
  일반적인 소팅은 두개의 자료를 교환하는 절차가 있습니다.
  이때 인덱스를 저장한 배열도 같이 교환시켜주면되는 거죠.. 간단합니다.
    swap(a(i),a(j); 에서 끝나지 않고 swap(idx(i),idx(j)); 해주는 거죠.

답변 1. 위에 방법으로 정렬을 끝낸후 원 인덱스 위치에서 나머지 컬럼들의 내용을 가져오면 됩니다.

정렬에서 또한가지 필요한 것은 동일한 자료가 있을경우 두번째 소팅키가 필요합니다.
물론 두개이상의 소팅키를 필요로하는 소팅도 있습니다.
이럴경우에는 소팅자료를 새롭게 만들어줍니다.
저는 모든 키에 해당하는 컬럼 내용을 하나의 문자열 자료로 만들어서 1차원 배열을 만듭니다.
그런후 정렬을 하면 모든 키가 적용된 소팅이 됩니다.
이때는 문자열 맨뒷부분에 인덱스를 포함해서 소팅한후 인덱스를 다시 복구하면 됩니다.

숫자를 소팅하는 경우에는 일반적으로 우측정렬된 숫자를 기준으로 정렬해야하며
이경우에도 숫자가 음수를 포함한다면 내용이 더 힘들어집니다.

소팅은 그리 쉽지 않은 작업입니다.
소팅에 많은 시간을 투자하신다면 모를까
advstringgrid를 그냥 사용하시는 것이 제일 편하실것 같습니다.

배열에서 뜬금없이 컬럼이야기가 나와서 한참을 생각했네요...

쉽게 생각하세요... 여러 컬럼(?)들을 하나의 레코드(묶음)라고 생각하시고 소트를 하세요. 이렇게 되면 1차원 배열 소트하는것과 똑같습니다.